2day

给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

进阶:你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现?

示例 1:

输入:nums = [1,2,1,3,2,5]

输出:[3,5]
解释:[5, 3] 也是有效的答案。

示例 2:
输入:nums = [-1,0]

输出:[-1,0]

示例 3:

输入:nums = [0,1]
输出:[1,0]

提示:
  • 2 <= nums.length <= 3 * 104

  • -231 <= nums[i] <= 231 - 1

  • 除两个只出现一次的整数外,nums 中的其他数字都出现两次

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/single-number-iii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

一、按常规思路,找相同的数,去掉,然后就剩了下只出现一次的数

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* singleNumber(int* nums, int numsSize, int* returnSize){
    
    for(int i = 0;i < numsSize;i++){
        for(int j = i+1;j < numsSize;j++){
            if(nums[i] == nums[j])
        }
    }
}

代码写到这里我先放弃了,换了其他思路写

二、递归

通过递归去掉相同的数,最后保留的数组即为最终结果。
遇到的难点是如果对比的数,没有相同的数,怎样保证不出现死循环。

一开始出现的错误
2day

猜想:
singleNumber()函数中应该每次把x置空。。。

leetcode多次调用singleNumber()函数,但是x在不断递增,导致非法访问内存

不过设置int x的那段多余了,直接删掉。逃避一下错误

然后就天道好轮回,苍天饶过谁,还是这个错误
2day

代码(待修改)

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 
//递归

int* singleNumber(int* nums, int numsSize, int* returnSize){
    int flag = 0;   //当有两个数相同时,flag=1,两个相同的数删掉;当不同时,保留数组
    int sameNumPos; //相同数字的位置
                    //但有个问题,如果第一个数只出现一次,被保留下来,将永远循环下去(死循环)
    int returmNums[1000];
    int pos = 0;    //新建数组中存放数的位置
    for(int i = 1;i < numsSize; i++){
        if(nums[0] == nums[i]){
            flag++;
            sameNumPos = i;
        }
    }
    if(flag == 1){
        for(int j = 0; j < sameNumPos; j++){           //到相同数位置的前一个数停止
            nums[j] = nums[j+1];
        }
        for(int m = sameNumPos-1; m < numsSize-2; m++){//整个数组的长度减2
            nums[m] = nums[m+2];                       //举例子,写在纸上,能够更直观的了解是否-1
        }
        numsSize = numsSize-2;
        singleNumber(*nums, numsSize ,*returnSize);
    }else{         //难点所在,怎样保证不出现死循环,并保证正确性。
                   //我的想法是将nums的第一个数存进新建一个数组,然后将后面的数递归
        returmNums[pos] = nums[0];
        for(int i = 0;i < numsSize ; i++){
            nums[i] = nums [i+1];
        }
        numsSize--;
        singleNumber(*nums, numsSize ,*returnSize);
    }
    return returmNums;
}

三、异或(永远的神!!!)

首次错误
2day
怀疑是数组的输出形势错了,我直接敲的代码是“return(数组)”
自己写的代码,不知道错在哪里555

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 
//异或
int* singleNumber(int* nums, int numsSize, int* returnSize){
    int x = 0; //与数组中的各个数进行异或运算,然后比较
    int com;
    int reNums[1000];
    int j = 0;
    for(int i = 0; i < numsSize;i++){
        x = x^nums[i]; 
    }
    //将每个除它本身外的数异或运算,如果结果与x
    for(int m = 0;m < numsSize;m++){
        int flag = 0; //初始化
        for(int n = 0;n < numsSize;n++){
            if(m!=n){
                flag = flag^nums[n];
            }
        }
        com = x^nums[m];
        if(com != flag){
            reNums[j] = nums[m];
            j++;
        }
    }
    return reNums;
}

网上的答案

int*singleNumber(  int* nums,         int numsSize,        int*returnSize )
{
   int ret=0;//0和如何元素异或都不会改变其结果,我们用0去异或
       for(int i=0;i<numsSize;i++)
          {
               ret^=nums[i];
          }
   int m=0;//找出ret第m位为1
        while(m<32)
          {
              if(ret & (1<<m))
              //与上1左移m位,ret中一定有一位是1,只需要不断地将m左移一位,当第ret的第m位为1时,if语句里不为0,进入if,break跳出去,得到m的值
              break;
              else
              ++m;
          }
//做完以上步骤,我们接下来分离ret中所有m位为1和m位为0的元素,其中一组为x1,另一组为x2
int x1=0,x2=0;
         for(int j=0;j<numsSize;j++)
         {
         if(nums[j]&(1<<m))
         {
           x1^=nums[j];//m为1进入if,到x1相互异或,最后相同的消失,只剩一个m位为1的独立元素
           }
           else
           {
           x2^=nums[j];//m为0不会进入if,到x2相互异或,最后相同的消失,只剩一个m位为0的独立元素
           }
         }
         int*retArr=(int*)malloc(sizeof(int)*2);
         retArr[0]=x1;
         retArr[1]=x2;
         *returnSize=2;
         return retArr;
}

但那个大佬的答案也出现了错误
left shift of 1 by 31 places cannot be represented in type 'int' [solution.c]
翻译:“int”类型[solution.c]无法表示1乘31位的左移位

四、排序

将数组排序,然后临近的两两对比,相同就将后面的数向前移动两位,不同就继续比较

本篇的代码每一个对的,明天查错

上一篇:2021-09-06


下一篇:[解题报告]《算法零基础100讲》(第17讲) 线性枚举(一) - 最值算法(1)(2)