@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
- 将没有缺得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中就返回另一个数
在这里插入图片描述
