该部分是力扣有关数组的OJ题（为了熟悉复杂度），点标题链接就能跳到相应题目
（没了解过力扣刷题的可以去搜搜力扣的出题方式）
比如：int* returnSize:这个参数是用来保存返回的数组的长度的，对于刚刷数组的同学需要注意，要给它赋值以返回数组的长度，不然是不可以的。（另一些参数是什么猜不到可以搜）
（还有力扣C语言一般是给你一个函数，你只需要实现这个函数就行，头文件什么的都包有了）
一.面试题 17.04. 消失的数字
数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。
你有办法在O(n)时间内完成吗？
示例 1：
输入：[3,0,1]
输出：2
示例 2：
输入：[9,6,4,2,3,5,7,0,1]
输出：8
求和法：
时间O（N） 空间O（1）
由观察可知，缺少的数字等于0~n数字之和减去0~n除了所缺少数字外其他数字之和。
//求和法 时间O（N） 空间O（1） int missingNumber(int* nums, int numsSize) { int x = 0; for (int i = 0;i <= numsSize;i++) { x += i; } for (int i = 0;i < numsSize;i++) { x -= nums[i]; } return x; }
异或法：
（此时就是在一堆数字中找只出现一次的数字了（找一个单身狗））
（下题是找两个单身狗的题）单身狗题目讲解：
C语言进阶21收尾(编程练习)(atoi,strncpy,strncat,offsetof模拟实现+找单身狗+宏交换二进制奇偶位）_从右向左奇数位和减偶数位和编程-CSDN博客
时间O（N） 空间O（1）
首先要明白什么是异或（异或就是二进制位的数值，相等则为0，不相等则为1）
假设a!=b，则有以下公式：
a^a = 0;
a^b = b^a;
0^a = a;
根据公式可以想到：
先将0~n的所有数字全部异或
ret1 = 0^1^……^n;
再将数组（缺失数字）中的数全部异或
ret2 = nums[0]^nums[2]^……^nums[numsSize-1];
最后将ret1和ret2异或，所得结果就是缺失的数字。
//异或法 时间O（N） 空间O（1） int missingNumber(int* nums, int numsSize) { int x = 0; for (int i = 0;i <= numsSize;i++) { x ^= i; } for (int i = 0;i < numsSize;i++) { x ^= nums[i]; } return x; }
二. 剑指 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]
限制：
- 2 <= nums.length <= 10000
解析：
（找两个单身狗）
如果我们按照之前的思路直接异或 肯定只会出来一个四不像数
假设数组1 2 3 3 1 4
我们把 两个单身狗分成两个组
而组中其他的数字就都不是单身狗
此时我们在分组异或就分别得到了2个单身狗
问题 我们以什么为依据分组？
依据 二进制位 异或把相同的数字变成0，不同的数字变成1，
我们根据1在哪位 就说明单身狗这个的二进制位不同 ，按照这个二进制位分
两个单身狗是不可能进到一组的
① 我们依然把数组中所有数字异或到一起 然后判断这个数字的二进制位 因为有两个单身狗2和4
0010 和0100最后异或完毕得到的二进制位是 0110 说明两个单身狗数字的二进制最后位是相等
我们左移一位得到了1 就说明 两个单身狗数字的倒数第二位二进制数 不相等
② 让数组中所有的数字左移一位 如果等于 1 放进第一个数组中
如果等于0 放进第二个数组中
③ 把数组中的数字全部异或就得到了 2个单身狗
异或法：
时间O（N） 空间O（1）
int* singleNumbers(int* nums, int numsSize, int* returnSize){ int *arr=(int*)calloc(2 , sizeof(int)); int sum = 0; for (int i = 0; i < numsSize; i++) { sum ^= nums[i]; } int count = 0; for (int i = 0; i < 32; i++) { if (sum & 1 << i) //循环判断第几位是1 { count = i;//如果是1 记录下来 break; } } for (int i = 0; i < numsSize; i++) { if (nums[i] & 1 << count) { arr[0] ^= nums[i]; } else { arr[1] ^= nums[i]; } } *returnSize = 2; printf("[%d,%d]",arr[0],arr[1]); return arr; }
三. 189. 轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出:[5,6,7,1,2,3,4]解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2 输出：[3,99,-1,-100] 解释:向右轮转 1 步: [99,-1,-100,3]向右轮转 2 步: [3,99,-1,-100]
提示：
- 1 <= nums.length <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
- 0 <= k <= 10^5
进阶：
- 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
- 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
暴力旋转法（超时）：
时间O（N*K） 空间O（1）
暴力旋转 和以前写过的字符串左旋一样，但时间过不了。
法三的三步旋转法我们也在这篇博客讲过：
C语言进阶⑬(字符串函数)+(指针编程题)strlen+strcpy+strcat+strstr+strtok+strerror_字符串指针函数创建-CSDN博客
//法一：移首补尾法 时间O（N*K） 空间O（1） void rotate(int* nums, int numsSize, int k) { for (int j = 0;j < k;j++) { int tmp = nums[numsSize - 1]; for (int i = numsSize - 1;i >= 1;i--) { nums[i] = nums[i - 1]; } nums[0] = tmp; } }
开辟新空间：
时间O(N) 空间O(N)
以额外的空间换取时间；开辟额外的数组进行存储。
//法二：开辟新空间 时间O(N) 空间O(N) void rotate(int* nums, int numsSize, int k) { k %= numsSize;//k可能大于numsSize int arr[100000] = { 0 }; int j = 0; for (int i = (numsSize - k);i <= (numsSize - 1);i++, j++) { arr[j] = nums[i]; } for (int i = 0;i <= (numsSize - k - 1);i++, j++) { arr[j] = nums[i]; } for (int i = 0;i <= numsSize - 1;i++) { nums[i] = arr[i]; } }
三步旋转法：
//法三：三步旋转法 时间O(N) 空间O(1) void reverse(int* nums, int left, int right) { while (left < right) { int tmp = nums[left]; nums[left] = nums[right]; nums[right] = tmp; left++; right--; } } void rotate(int* nums, int numsSize, int k) { k %= numsSize; reverse(nums, numsSize - k, numsSize - 1);//1 旋转右部分 reverse(nums, 0, numsSize - k - 1);//2 旋转左部分 reverse(nums, 0, numsSize - 1);//3 整体旋转 }
数据结构与算法②(复杂度相关OJ)(六道数组OJ题)（下）：https://developer.aliyun.com/article/1513314
