有关时间复杂度和空间复杂度的练习_常见的时间空间复杂度选择题

目录

一、消失的数字

二、轮转数组

三、 单选题

---

---

一、消失的数字

数组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;
		else
			break;
	}
	return ans;
}

该算法的时间复杂度为 O(n)，因此正确答案是 A。