系列文章目录
🎈 🎈 我的CSDN主页:OTWOL的主页，欢迎！！！👋🏼👋🏼
🎉🎉我的C语言初阶合集：C语言初阶合集，希望能帮到你！！！😍 😍
🔍🔍我的C语言进阶合集：我的C语言进阶合集，期待你的点击！！！🌈🌈
🎉🎉我的数据结构与算法合集：数据结构与算法合集，点进去看看吧！！！ 🎊🎊
文章目录
- 系列文章目录
- 前言
- 一、消失的数字
- 题目分析：
- 方法 1
- 方法 2
- 二、轮转数组
- 题目分析：
- 方法 1
- 方法 2
- 方法 3
- END
前言
各位博友，大家好！👋 今天为大家送上数组有关的
OJ练习的总结🔍。
一、消失的数字
想要挑战一下的小伙伴们，快来点击下面的链接吧！🔗
让我们来看看，到底谁的方法更胜一筹，比拼一下智慧与创意，嘻嘻~ 😉🧠✨
消失的数字
题目分析：
数组 nums 包含从 0 到 n 的所有整数，但其中缺了一个。
方法1：可以使用异或操作符来解决
思路如下：
两个相同的数字进行异或（^），得到的结果是数字0，
数字0与其他数字异或（^），得到的是该数字本身。
我们可以先将该数组的所有数字进行异或，
再将【0，n】的数字和该数组的异或结果进行异或（^），
最终就能得到那个缺失的整数。
原因很简单，那个消失的数字就出现了一次，其他数字出现了两次，
当进行异或（^）时，其他数字出现了两次，异或得到的结果是数字0，
最终就是数字0和消失的数字进行异或（^），
结果就是那个缺失的整数。
方法 2：可以使用相减的方法
参考 方法 1，可以先将该数组的所有数字进行相加，得到
sum1；
再将【0，n】的数字进行相加，得到sum2；
最后返回sum2 - sum1。
原因很简单，那个消失的数字就出现了一次，其他数字出现了两次。
当进行相减时，那个消失的数字就是sum2 - sum1。
方法 1
int missingNumber(int* nums, int numsSize)
{int i = 0; // 定义循环变量 i ，用于遍历数组int ret = 0; // 定义返回值变量 ret ，用于存储异或结果// 将该数组的所有数字进行异或for(i = 0; i < numsSize; ++i) {ret ^= nums[i]; // 异或操作，将数组中的每个元素与 ret 进行异或}// 将【0，n】的数字和该数组的异或结果 ret 进行异或// 这里的 n 是数组的长度 numsSizefor(i = 0; i <= numsSize; ++i) {ret ^= i; // 将 0 到 numsSize 的每个数字与 ret 进行异或}return ret; // 返回最终的异或结果，即为缺失的数字
}
方法 1 的 时间复杂度是
O(numsSize)， 空间复杂度是O(1)。
方法 2
int missingNumber(int* nums, int numsSize)
{int i = 0; // 定义循环变量 i，用于遍历数组int sum1 = 0; // 定义变量 sum1，用于存储数组中所有数字的和int sum2 = 0; // 定义变量 sum2，用于存储从 0 到 numsSize 所有数字的和// 将该数组的所有数字进行相加，得到 sum1for(i = 0; i < numsSize; ++i) {sum1 += nums[i]; // 累加数组中的每个元素}// 再将【0，n】的数字进行相加，得到 sum2// 这里的 n 是数组的长度 numsSizefor(i = 0; i <= numsSize; ++i) {sum2 += i; // 累加从 0 到 numsSize 的每个数字}return (sum2 - sum1); // 返回 sum2 和 sum1 的差值，即为缺失的数字
}
方法 2 的 时间复杂度是
O(numsSize)， 空间复杂度是O(1)。
二、轮转数组
下面是这道题目的链接🔗，想尝试的博友，可以点击下面的链接直达哦 👋🏼
轮转数组
题目分析：
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
首先，要将
k %数组的长度（numsSize）。
因为，第k次轮转其实就是第0次轮转。
方法 1
可以先将最右边（末尾）的那个元素保存起来，
再将前 n - 1 个元素向后移动一个位置，
上面是循环的一次，如此循环，一直到 k 次，最终就能得到轮转后的结果。
但是该方法超出了时间限制（即当有一个数组长度比较大的，通过时间要很长）。
方法 2
可以将数组的后面
k个元素保存到一个新的数组中，
再将原来数组的前面n - k个元素尾插到新数组中。
最后将 新数组中的所有值 依次赋值给 原来的数组。
但是该方法也是超出了时间限制。
方法 3
是比较难想到的方法，
该方法是先将数组的后面k个元素进行逆序，
再将数组前面的numsSize - k个元素 进行逆序，
最后将该数组 整体 逆序。
// 交换数组中两个位置的元素的函数
void Swap(int* nums, int left, int right)
{while(left < right) {int tmp = nums[left]; // 临时变量，用于交换数值nums[left] = nums[right]; // 将 right 位置的值赋给 left 位置nums[right] = tmp; // 将临时变量的值（原 left 位置的值）赋给 right 位置++left; // 移动 left --right; // 移动 right }
}// 旋转数组的函数，将数组 nums 向右旋转 k 个位置
void rotate(int* nums, int numsSize, int k)
{k %= numsSize; // 取模操作，确保 k 不超过数组长度，因为旋转数组长度圈数后会回到原样// 将最后 k 个元素 逆序Swap(nums, numsSize - k, numsSize - 1);// 将前 numsSize - k 个元素 逆序 Swap(nums, 0, numsSize - k - 1);// 将整个数组 逆序Swap(nums, 0, numsSize - 1);
}
方法 3 的 时间复杂度是
O(numsSize)， 空间复杂度是O(1)。
END
每天都在学习的路上！
On The Way Of Learning
