目录
一：旋转数组
思路：
二：消失的数字
思路：
一：旋转数组
189. 轮转数组 - 力扣（LeetCode）
给定一个整数数组
nums，将数组中的元素向右轮转k个位置，其中k是非负数。
这道题和【C语言】系列里面有道题很像-《旋转字符》
我们先回顾一下《旋转字符》的思路
实现一个函数，可以左旋字符串中的k个字符。
例如：
abcdef左旋两个字符得到cdefab
采取 " 三 步 翻 转 法 "
第一步:左旋数组左边 (0~k-1) K为分界点
第二步：左旋剩余的字符(k~end)
第三步：整个数组全部逆序交换(0~end)
注：这里的k记得%字符长度;防止越界
void reverse(char* left, char* right)
{
//逆序函数需要两个指针分别指向前面和后面，当前面指针小于后面指针时
//说明还有元素需要逆序
while (left < right)
{
char tmp = *left;
*left = *right;
*right = tmp;
left++;
right--;
}
}
int main()
{
char arr[] = "abcdef";
int len = strlen(arr); //获取字符串长度
int k = 0; //左旋数
scanf("%d", &k);
printf("左旋前：%s\n", arr);
k %= len; //防止k越界
//写一个逆序函数reserve
//先逆序左边
reverse(arr, arr + k - 1);
//再逆序右边
reverse(arr + k, arr + len - 1);
//再整体逆序
reverse(arr, arr + len - 1);
printf("左旋后：%s\n", arr);
return 0;
}
但是此题，又略有不同，因为该数组元素是整型，和上面left，right数值会引起冲突
比如在第三次交换前的时候，该题数值已经变成了 4321765;
如果按照思路，此时left =4,right=5;只能交换一次就会失败；达不到最终数值样子
思路：
我们将left,right不采取数组值，将以数组下标处值进行 while循环 交换 数组值元素；
这样我们可以避免数组值和数组下标值数字冲突，造成了error;
第一步：翻转所有数值
第二步：翻转数组k-1前范围的数值
第三步: 翻转k到end 的值
切记！这里的left，right值是下标处值，而不是数组值；
k%=len； 防止输入的k导致数组越界
void Swap(int* left,int* right)
{
int tmp = *left;
*left = *right;
*right = tmp;
}
void reserve(int* nums, int left, int right)
{
while (left < right)
{
//取出下标处地址，进行解引用交换
Swap(&nums[left], &nums[right]);
left++;
right--;
}
}
void rotate(int* nums, int numsSize, int k)
{
k%=numsSize;//防止越界
//以下标处数值来当作left,right，用来循环，避免下标处和数组数值冲突
reserve(nums, 0, numsSize - 1);
reserve(nums, 0, k - 1);
reserve(nums, k, numsSize - 1);
}二：消失的数字
面试题 17.04. 消失的数字 - 力扣（LeetCode）
数组
nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
思路：
1.冒泡排序
先冒泡排序，把数据遍历好顺序位置
遍历，当前值+1，不等于下一个数字 就是这个数
2.采取异或 操作符
假设数组为 0 1 2 3 4 5 6 7 9; （从0~n）
我们生成一组不缺少数字：0 1 2 3 4 5 6 7 8 9
这两组数组都异或一遍，因为异或的原理，只会剩下只出现一次的那个数字 8
^： //按位异或
如果其中一个操作数中的位为 0，而另一个操作数中的位为 1，则相应的结果位设 置为 1。 否则，将对应的结果位设置为 0。相同为0，不同为1 a^a =0；0^5 =5；(支持交换律)
按位异或 ^ 是一种二进制运算符，它将两个数的每一位进行异或操作。
异或运算的规则是：如果两个对应位的数相同，则该位结果为0；如果两个对应位的数不同，则该位结果为1。异或运算有以下几个特点：
0 ^ 0 = 0，0 ^ 1 = 1，1 ^ 0 = 1，1 ^ 1 = 0，这是异或运算的基本规则。
0异或任何数等于任何数本身，即0 ^ x = x。
1异或任何数等于该数的取反，即1 ^ x = ~x。
任何数异或自己等于0，即x ^ x = 0。
注：操作数必须是整数
int missingNumber(int* nums, int numsSize){
int x = 0;
int i =0;
for(i=0;i<numsSize;i++)
{
x^=nums[i];
}
for(i=0;i<=numsSize;i++)
{
x^=i;
}
return x;
}
3. 等差数列公式求和
（不缺少数字）我们将0~n的数字累计加起来；得到sum
再用sum 逐步减去(缺少数字)数组数据；剩下的数就是缺少的数
int missingNumber(int* nums, int numsSize)
{
int N = numsSize;
int sum = ((0 + N) * (N + 1))/ 2; //根据等差数列公式 （（首相 + 尾项） *（相数））/2
int i = 0;
for (i = 0; i < numsSize; i++)
{
sum -= nums[i]; //不缺少数字的累加 减去 缺少数字的数据
}
return sum;
}
int main()
{
int nums[] = { 0,1,2,3,4,5,6,7,9 };
int numsSize = sizeof(nums) / sizeof(nums[0]);
int num = missingNumber(nums, numsSize);
printf("%d\n", num);
return 0;
}
文章来源：https://www.toymoban.com/news/detail-721347.html
文章来源地址https://www.toymoban.com/news/detail-721347.html
到了这里，关于【数据结构】面试OJ题——时间复杂度的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
