复杂度相关OJ题（LeetCode、C语言、复杂度、消失的数字、旋转数组）

两道关于复杂度的LeetCode OJ题

1. 消失的数字
2. 轮转数组

代码：C语言

1. 消失的数字

点击前往LeetCode查看消失的数字

1.1 题目描述

要求 ：时间复杂度要在O(n)内

1.2 解决思路及代码实现

1.2.1 思路1

1. malloc一个额外的个数为n+1的数组，并全部初始化为-1。
2. 遍历要输入的数据，这个数是多少，就填写到该数组对应位置。
3. 再遍历一遍该数组，哪个位置是-1，那么哪个位置的下标就是缺失的数字。
   
   ps：Drawio的绘图很不错！！！有需要的可以导Microsoft Store搜索应用Drawio，直接下载正版。

---

• 时间复杂度：O(n)，符合题目要求
• 空间复杂度：O(n)
• 代码部分也比较简单，这里就不实现了。

1.2.2 思路2

• 使用异或，这里先给大家补充一下异或的知识。
• 什么是异或？
  在逻辑学中，逻辑算符异或（exclusive or）是对两个运算元的一种逻辑析取类型，符号为 XOR 或 EOR 或 ⊕（编程语言中常用^）。
  但与一般的逻辑或不同，异或算符的值为真仅当两个运算元中恰有一个的值为真，而另外一个的值为非真。转化为命题，就是：“两者的值不同。”或“有且仅有一个为真。”
• 异或的特性：

1. 相同的两个数异或的结果为0。
2. 异或不分顺序。按位异或，相同为0，相异为1。
3. 0和任何数异或结果为该数本身

---

下面进入正题，解决思路如下：

1. 创建一个变量x，并赋初值为0
2. x跟输入的数据都异或一遍
3. x和0~n之间的数都异或一遍，最后的x即为缺失的数字

C语言代码实现如下：

int missingNumber(int* nums, int numsSize) {
    
	int x = 0;
	for (int i = 0; i < numsSize; ++i)
	{
    
		x ^= nums[i];
	}
	for (int j = 0; j < numsSize+1; ++j)
	{
    
		x ^= j;
	}
	return x;
}

1. 时间复杂度：O(n)
2. 空间复杂度：O(1)

---

2. 轮转数组

点击前往LeetCode查看轮转数组

2.1 题目描述

轮转数组（旋转数组）要求如下：

1. 想出三种不同的解决方法
2. 时间复杂度O(n)
3. 空间复杂度O(1)

2.2 解决思路及代码实现

2.2.1 思路1

1. 每次旋转一个
2. 旋转K次

---

• 时间复杂度：O(N^2)
• 空间复杂度：O(1)
• 不符合要求（过不了OJ）

2.2.2 思路2

以空间换时间

1. 开辟一个额外的数组
2. 把原数组的后k个数据拷贝到新数组的前k个位置
3. 把原数组的前n-k个数据拷贝到新数组的后n-k个位置
4. 再将新数组拷贝回原数组，旋转结束
   

---

• 时间复杂度：O(n)
• 空间复杂度：O(n)
• 不符合要求（但能过OJ）

2.2.3 思路3

• 原地逆置

1. 前n-k个逆置
2. 后k个逆置
3. 整体逆置
   

---

• 时间复杂度：O(n)
• 空间复杂度：O(1)
• 符合题意，是最优解法也最难想到

C语言代码实现如下：

int* reverse(int* nums, int left, int right)
{
    
	while (left < right)
	{
    
		int tmp = nums[left];
		nums[left] = nums[right];
		nums[right] = tmp;
		left++;
		right--;;
	}
	return nums;
}

void rotate(int* nums, int numsSize, int k) {
    
	k %= numsSize;
	reverse(nums, numsSize - k, numsSize - 1);
	reverse(nums, 0, numsSize - k - 1);
	reverse(nums, 0, numsSize - 1);
}

---

学习记录：

• 本篇整理于2022.6.21
• 如果有错误的地方请多多指教