有关时间复杂度和空间复杂度的练习

目录

一、消失的数字

二、轮转数组

三、 单选题

---

---

一、消失的数字

数组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. 1 2 3 4 | 5 6 7，即根据 k 将整数数组 nums 分为左右两个部分。

2. 4 3 2 1 | 7 6 5，它是分别逆序左右两个部分后得到的结果。

3. 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。