题一：旋转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
思路一：
创建reverse()函数传入三个值分别为数组地址，从第几个数组元素开始，结束元素位置；
在reverse（）函数中实现颠倒，swap()函数实现交换。
先将数组分为两部分0--(k-1)和k--(sz-1),然后分别旋转；
//交换位置 void swap(int* a, int* b) { int t = *a; *a = *b, *b = t; } //实现颠倒 void reverse(int* nums, int start, int end) { while (start < end) { swap(&nums[start], &nums[end]); start += 1; end -= 1; } } //起始位置 void rotate(int* nums, int numsSize, int k) { int sz = numsSize; int i = 0; int j = 0; int tmp = 0; k = k % sz; reverse(nums,0,sz-1); reverse(nums,0,k-1); reverse(nums,k,sz-1); }
思路二：
如图：
void rotate(int* nums, int numsSize, int k) { int* tmp = (int*)malloc(sizeof(int) * numsSize); k = numsSize % k; memcpy(tmp, nums + numsSize - k, sizeof(int) * k); memcpy(tmp+k, nums, sizeof(int) * (numsSize - k)); memcpy(nums, tmp , sizeof(int) * numsSize); }
题二：消失的数字
数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
思路一：
将0--n的数全部加起来，然后减去数组中的值，最后得到的结果就是消失的数。
int missNumber(int* nums, int numsSize) { int N = numsSize; int ret = N * (N + 1) / 2; for (int i = 0; i < N; i++) { ret -= nums[i]; } return ret; }
思路二：
单身狗问题解法：异或“ ^ ”
时间复杂度：O(N)
解法：定义一个数tmp为0，与0--n的数进行异或，然后与题所给的数组进行再次异或，
得出消失的数；
基础：a^a=0;a^b^a=b;
int missingNumber(int* nums, int numsSize) { int n = numsSize; int i = 0; int tmp = 0; for(i = 0; i <= n;i++ ) { tmp ^= i; } for(i = 0;i < n;i++) { tmp ^= nums[i]; } return tmp; }
题三：移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
思路一：
解题思路：
1. 从前往后遍历nums，找到val第一次出现的位置
2. 将val之后的所有元素整体往前搬移，即删除该val
3. nums中有效元素个数减少一个
循环进行上述操作，直到nums中所有值为val的元素全部删除完
时间复杂度:O(N^2) 空间复杂度:O(1)
int removeElement(int* nums, int numsSize, int val) { // while (1) { // 1. 在nums中找val出现的位置 int pos = 0; for (; pos < numsSize; ++pos) { if (nums[pos] == val) { break; } } // 2. 检测是否找到 if (pos == numsSize) break; // 3. 找到值为value的元素--将其删除 for (int j = pos + 1; j < numsSize; ++j) { nums[j - 1] = nums[j]; } numsSize--; } return numsSize; }
思路二：
解题思路:
因为题目说了，数组中元素个数最大为100，所以不用动态申请，至二级创建100个元素数组即可
1. 创建一个100个元素的整形数组temp
2. 遍历nums，将nums中所有与val不同的元素搬移到temp中
3. 将temp中所有元素拷贝回nums中
时间复杂度: O(N) 空间复杂度: O(N)
int removeElement(int* nums, int numsSize, int val) { // 1. 申请numSize个元素的新空间 int temp[100]; // 2. 将nums中非value的元素搬移到temp中---尾插到temp中 int count = 0; for (int i = 0; i < numsSize; ++i) { if (nums[i] != val) { temp[count] = nums[i]; ++count; } } // 3. 将temp中删除val之后的所有元素拷贝到nums中 memcpy(nums, temp, sizeof(int) * count); return count; }
思路三：
解题思路:
1. 设置一个变量count，用来记录nums中值等于val的元素的个数
2. 遍历nums数组，对于每个元素进行如下操作：
a. 如果num[i]等于val，说明值为val的元素出现了一次，count++
b. 如果nums[i]不等于元素，将nums[i]往前搬移count个位置
因为nums[i]元素之前出现过count个值等于val的元素，已经被删除了
因此次数需要将nums[i]往前搬移
3. 返回删除之后新数组中有效元素个数
时间复杂度：O(N) 空间复杂度：O(1)
int removeElement(int* nums, int numsSize, int val) { int count = 0; for (int i = 0; i < numsSize; ++i) { if (nums[i] == val) { count++; } else { nums[i - count] = nums[i]; } } return numsSize - count; }
做错的选择题：
分析以下函数的时间复杂度
void fun(int n) { int i=l; while(i<=n) i=i*2; }
A.O(n)
B.O(n^2)
C.O(nlogn)
D.O(logn)
答案：D
解析: 此函数有一个循环，但是循环没有被执行n次，i每次都是2倍进行递增，所以循环只会被执行log2(n)次。
给定一个整数sum，从有N个有序元素的数组中寻找元素a，b，使得a+b的结果最接近sum，最快的平均时间复杂度是（ ）
A.O(n)
B.O(n^2)
C.O(nlogn)
D.O(logn)
答案：A
解析：此题目中，数组元素有序，所以a,b两个数可以分别从开始和结尾处开始搜，根据首尾元素的和是否大于sum,决定搜索的移动，整个数组被搜索一遍，就可以得到结果，所以最好时间复杂度为n
分析以下函数的空间复杂度（ ）
int** fun(int n) { int ** s = (int **)malloc(n * sizeof(int *)); while(n--) s[n] = (int *)malloc(n * sizeof(int)); return s; }
A.O(n)
B.O(n^2)
C.O( 1 )
D.O(nlogn)
解析：此处开辟的是一个二维数组，数组有n行，每行分别有1,2,3,...n列，所以是n(n + 1)/2个元素空间，空间复杂度为n^2
