有关时间复杂度和空间复杂度的练习
目录
一、消失的数字
二、轮转数组
三、 单选题
一、消失的数字
数组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 ans = 0;for (int i = 0; i <= numsSize; ++i){ans ^= i;}for (int i = 0; i < numsSize; ++i){ans ^= nums[i];}return ans;
}代码实现二（使用等差数列求和公式）：
int missingNumber(int* nums, int numsSize)
{int sum = numsSize * (numsSize + 1) / 2;for (int i = 0; i < numsSize; ++i){sum -= nums[i];}return sum;
}以上两种算法的时间复杂度都是 O(n)，空间复杂度都是 O(1)。
二、轮转数组
给定一个整数数组 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)的 原地 算法解决这个问题吗？
代码实现一：
void rotate(int* nums, int numsSize, int k)
{k %= numsSize;int* tmp = (int*)malloc(sizeof(int) * k);if (NULL == tmp){perror("malloc failed!");return;}// 首先把数组后面的 k 个元素存放到 tmp 指向的临时空间中int j = 0;for (int i = numsSize - k; i < numsSize; ++i){tmp[j++] = nums[i];}// 然后把数组前面的 numsSize - k 个元素按从后往前的顺序依次往后移动 k 个位置for (int i = numsSize - k - 1; i >= 0; --i){nums[i + k] = nums[i];}// 最后再将存放在临时空间中的 k 个元素放回数组中for (int i = 0; i < k; ++i){nums[i] = tmp[i];}free(tmp);tmp = NULL;
}该算法的时间复杂度是 O(n)，空间复杂度是 O(k)。
代码实现二：
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, 0, numsSize - k - 1);reverse(nums, numsSize - k, numsSize - 1);reverse(nums, 0, numsSize - 1);
}该算法的时间复杂度是 O(n)，空间复杂度是 O(1)。
分析（示例一）：
1 2 3 4 | 5 6 7，即根据k将整数数组nums分为左右两个部分。
4 3 2 1 | 7 6 5，它是分别逆序左右两个部分后得到的结果。
5 6 7 | 1 2 3 4，它是整体逆序后得到的结果。在逆序的过程中，越靠后的元素经过逆序后就会越靠前，因此整体逆序后，左右两部分的元素发生了互换，但由于之前已经分别逆序了左右两部分的元素，因此在第 3 步后，两部分的元素的顺序较一开始没有发生改变。
三、 单选题
给定一个整数 sum，从有 n 个有序元素的数组中寻找元素 a, b，使得 a + b 的结果最接近 sum，最快的平均时间复杂度是：
A、O(n)
B、O(nlogn)
C、O(n^2)
D、O(logn)
代码实现（假设数组是按非递减顺序排列）：
int* findClosestPair(int* nums, int numsSize, int sum, int* returnSize)
{*returnSize = 2;int* ans = (int*)malloc(sizeof(int) * 2);if (NULL == ans){perror("malloc failed!");return NULL;}int left = 0;int right = numsSize - 1;int dif = INT_MAX;while (left < right){int res = nums[left] + nums[right] - sum;if (abs(res) < dif) // 判断是否更新误差{ans[0] = nums[left];ans[1] = nums[right];dif = abs(res);}if (res < 0) // 此时 nums[left] + nums[x] < res < 0，其中 x < right++left;else if (res > 0) // 此时 nums[right] + nums[x] > res > 0，其中 x > left --right;elsebreak;}return ans;
}该算法的时间复杂度为 O(n)，因此正确答案是 A。