645. Wrong set

Topic link ：   645. The wrong set

Title Description

 

First of all How did I do it ？

I use for Loop traversal Wrote a lot of , Repeat the test , Finally, it was written I start running ; As a result, when I run He told me

I exceeded the time limit

I giao, I really appreciate .

int* findErrorNums(int* nums, int numsSize, int* returnSize){
    int i = 0;
    int* num_s = malloc(sizeof(int)*2);
    int loss = 0;
    int loss_1 = 0;
    *returnSize = 2;
    int flag = 0;
    int j = 0;
    for(i = 0;i < numsSize;i++)
    {
        for(j = 0;j<numsSize-i-1;j++)
        {
            int tmp = 0;
            if(nums[j]>nums[j+1])
            {
                tmp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = tmp;
            }
        }
    }
    for(i = 0;i<numsSize;i++)
    {
        for(j = 0;(j<numsSize&&i!=j);j++)
        {
           if(flag == 0)
            {
                if(nums[i] == nums[j])
                {
                    loss = nums[j];
                   flag = 1;
                }
            }
            
       }
    } 
    int t = 0;
    for(i = 0;i<numsSize;i++)
    {
        t++;
        if(nums[0] != 1)
        {
            loss_1 = 1;
        }
        else
        {
             if(nums[i] != t)
            {
                loss_1 = t;
                if(loss>loss_1)
                {
                    break;
              }
           }
       }
       
  }

num_s[0] = loss;
num_s[1] = loss_1;   
    return num_s;
}

  The above is for entertainment only ;

Here is the positive solution ;

int* findErrorNums(int* nums, int numsSize, int* returnSize){
    int i = 0;
    int* num_s = malloc(sizeof(int)*2);
    int loss = 0;
    *returnSize = 2;
    int j = 0;
    for(i = 0;i < numsSize;i++)
    {
        for(j = 0;j<numsSize-i-1;j++)
        {
            int tmp = 0;
            if(nums[j]>nums[j+1])
            {
                tmp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = tmp;
            }
        }
    }
    int tmp = 0;
    for(i = 0;i<numsSize;i++)
    {
        tmp = nums[i];
        if(tmp == loss)
        {
           num_s[0] = loss;
        }
        else if(tmp - loss>1)
        {
            num_s[1] = loss+1;
        }

        loss = tmp;
    }
    if(nums[numsSize-1] != numsSize)
    {
        num_s[1] = numsSize;
    }
    return num_s;
}

This is just a solution

One more Method of bit operation

Mention operators , We need to be familiar with and master Use of bitwise operators

& Bitwise AND        | Press bit or        ^ Bitwise XOR             （ notes ： Their operands must be integers .）

1. Bitwise AND

int main()
{
	int a = 3;
	int b = -5;
	int c = a & b;
	printf("c = %d\n", c);
	return 0;
}

Think about it ,C How much will it be ？

The result is C = 3

3 Original back Complement code （ The complement of positive numbers is the same ）
00000000000000000000000000000011
-5 The original code of
10000000000000000000000000000101  -5 The original code of
11111111111111111111111111111010  -5 The inverse of
11111111111111111111111111111011  -5 Complement
00000000000000000000000000000011  3 Complement
& Bitwise AND   Express 2 Base bit The same bit is   For one   Different bits （ Both are zero and zero ） zero   Then the calculation results by
00000000000000000000000000000011   by  3
therefore C = 3;

2. Press bit or

int main()
{
	int a = 3;
	int b = -5;
	int c = a | b;
	printf("c = %d\n", c);
	return 0;
}

Rethinking ：

11111111111111111111111111111011  -5 Complement
00000000000000000000000000000011  3 Complement
|  Press bit or   Express 2 Base bit   One for one   Just for one   Both are zero It's zero ;11111111111111111111111111111011   （-5 Complement ）

3. Bitwise XOR

int main()
{
	int a = 3;
	int b = -5;
	int c = a ^ b;
	printf("c = %d\n", c);
	return 0;
}

11111111111111111111111111111011 - 5 Complement
00000000000000000000000000000011  3 Complement
^ Press bit or    Express 2 Base bit    Same as zero Different into one ;
11111111111111111111111111111000(-8 Complement )
 

All of these are These are the basic rules for using bitwise operators ; Let's talk about it once Their simple nature ( Follow the law of exchange and the law of knot )

a^a = 0
0^a = a
a^b^a = b

I got it , Now we can analyze and solve the initial problem ;

Through analysis, we can know ：

Duplicate numbers appear in the array 2 Time , Missing numbers appear in the array 0  Time , Each remaining number appears in the array 1  Time . thus it can be seen , The parity of occurrence times of repeated numbers and missing numbers is the same , And it is different from the parity of the number of occurrences of each other number . If in the array n After the number, add from 1  To n  Every number of , obtain 2n A digital , It's in 2n Of the numbers , Repeated numbers appear 3  Time , The missing number appears 1 Time , Every other number appears 2  Time . According to the parity of the number of occurrences , You can use XOR to solve .

Code as follows

int* findErrorNums(int* nums, int numsSize, int* returnSize) {
    int* errorNums = malloc(sizeof(int) * 2);
    int xorSum = 0;
    for (int i = 1; i <= numsSize; i++) 
    {
        xorSum ^= i;               // Add a group of （1->n） The data of  
        xorSum ^= nums[i - 1];     //for  The loop ends   here xorSum  The result should be  
                                   // Repeat the numbers  ^  Missing number                                     
    }
    int lowbit = xorSum & (-xorSum);// We know   Negative and positive numbers   Is the difference between the 
                                    // The complement of a negative number is a positive number, which is inversed by bits   Add one to get 
                                    // therefore   here lowbit for xorSum The lowest point of ;
                                    // and  xorSum =  Repeat the numbers  ^  Missing number   
                                    // in other words    lowbit  Namely   The lowest different bits of repeated numbers and missing numbers 
   // utilize lowbit You can divide an array into two groups 
   // Each number in the first group  a All satisfied with  a & lowbit==0,
   // Each number in the second group  b All satisfied with  b & lowbit!=0 


    int num1 = 0, num2 = 0;
    for (int i = 0; i < numsSize; i++) 
    {
        if ((nums[i] & lowbit) == 0) 
    {
            num1 ^= nums[i];
        } else {
            num2 ^= nums[i];
        }
    }
    for (int i = 1; i <= numsSize; i++) 
    {
        if ((i & lowbit) == 0) 
    {
            num1 ^= i;
        } else {
            num2 ^= i;
        }
    }
    int* ret = malloc(sizeof(int) * 2);
    *returnSize = 2;
    for (int i = 0; i < numsSize; i++) 
    {
        if (nums[i] == num1) 
    {
            ret[0] = num1, ret[1] = num2;
            return ret;
        }
    }
    ret[0] = num2, ret[1] = num1;
    return ret;
}

 author ：LeetCode-Solution
 link ：https://leetcode.cn/problems/set-mismatch/solution/cuo-wu-de-ji-he-by-leetcode-

Now let's take a look at the standard answer  

author ：LeetCode-Solution
link ：https://leetcode.cn/problems/set-mismatch/solution/cuo-wu-de-ji-he-by-leetcode-solution-1ea4/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .