1. 消失的数字
题目描述
解题思路
异或操作符支持乘法交换律 ---> 0^3^0^1 ^0^1^2^3 ---> 0^0^0^1^1^3^3^2 --->相同的值异或为0 ---> 0^2 --->2
int missingNumber(int* nums, int numsSize){
int val = 0;
int i = 0;
for (i = 0; i < numsSize; i++)
{
val ^= nums[i];
}
for (i = 0; i <= numsSize; i++)
{
val ^= i;
}
return val;
}
时间复杂度 O(N), 空间复杂度 O(1)
2. 轮转数组
题目描述
解题思路
前n-k个逆置 ---> 4 3 2 1 后k个逆置 ---> 4 3 2 1 7 6 5 整体逆置 ---> 5 6 7 1 2 3 4void 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 n, int k){
int sign = k%n;
// 前n-k个逆置
reverse(nums,0,n-sign-1);
// 后个k个逆置
reverse(nums,n-sign,n-1);
// 整体逆置
reverse(nums,0,n-1);
}
时间复杂度 O(N), 空间复杂度 O(1)
标签:面试题,right,reverse,nums,int,---,数组,left From: https://www.cnblogs.com/xumu11291/p/17292111.html