@TOC

前言

这里的oj题全都是接口型 也就是只给出一个函数 填写即可

提示：以下是本篇文章正文内容，下面案例可供参考

一、剑指 Offer 56 - II. 数组中数字出现的次数 II

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1：
输入：nums = [3,4,3,3]
输出：4
示例 2：
输入：nums = [9,1,7,9,7,9,7]
输出：1

int singleNumber(int* nums, int numsSize){
    int i=0;
    int j=0;
    int count=0;
    for(i=0;i<numsSize;i++)
    {
        count=0;
        for(j=0;j<numsSize;j++)
        {
            if(nums[i]==nums[j])
            {
                count++;
            }
        }
        if(count==1)
        {
            return nums[i];
        }
    }
    return NULL;
}

只需要遍历 判断count是否为1 为1就返回
这道题难度竟然是中等
没有标记时间复杂度为多少 是在很容易做
给大家信心

二、面试题 17.04. 消失的数字

数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
注意：本题相对书上原题稍作改动

示例 1：
输入：[3,0,1]
输出：2

示例 2：
输入：[9,6,4,2,3,5,7,0,1]
输出：8

int missingNumber(int* nums, int numsSize){
    int i=0;
    int sum=0;
    for(i=0;i< numsSize;i++)
    {
        sum^=(nums[i]);
    }
    for(i=0;i<numsSize+1;i++)
    {
        sum^=i;
    }
    return sum;
    return 0;
}

这道题标记是简单 如果异或学的不好 无从下手
异或: 相同为0 相异为1
0到n共有n+1个数
而题中的0到n个数 中间缺少一个 所以是n个数
本题分为两步:
1.将输入（中间缺一个的所有数）全部异或在一起 赋值给sum
2. 将没有缺得0到n个数 与sum异或在一起

三、剑指 Offer 56 - I. 数组中数字出现的次数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* singleNumbers(int* nums, int numsSize, int* returnSize){
    int*ptr=(int*)malloc(2*sizeof(int));
    int ret=0;
    int i=0;
    for(i=0;i<numsSize;i++)//第一步
    {
        ret^=nums[i];
    }
    int n=0;
    for(i=0;i<32;i++)//第二步 因为第一步两者异或 一定有一位是1 
    {
        if((ret>>i)&1==1)// 从右向左  依次向右移位 跟1判断是否当前位为1
        {
            n=i;//如果是1就返回
            break;
        }
    }
    int num1=0;
    int num2=0;
    for(i=0;i<numsSize;i++)//第三步
    {
        if((nums[i]>>n)&1==1)
        {
            num1^=nums[i];
        }
        else
        {
            num2^=nums[i];
        }
    }
    ptr[0]=num1;//一定要注意的是 不要将ptr[0]和ptr[1]直接放在循环中异或 会报错
    ptr[1]=num2;
    *returnSize=2;//返回的是两个值
    return ptr;
}

此题难度为中等，感觉这个才是真的中等
需要得依然是异或
相同为0 ，相异为1
分为三步:
1.将所有的值异或，得到就是单个的两个数的异或 相异为1 所以一定有一位是1
…
2.我们想到就是通过二进制位中的同位1/0区分两个不同的数
…
3.先把要判断的数组移位到能够判断1/0的位上面
如果是1就返回sum1中 ,进行异或
如果为0就返回sum2中,进行异或
因为把不同的数放在不同的数组中 而数组中的其他数都是成对出现的，都可以异或为0
即sum1中就返回 一个数
sum2中就返回另一个数