我们的思路是将所有的数异或在一起,然后再将结果异或0-N,得到的最后结果就是消失的数字; 原理:a ^ a = 0 ; 0 ^ a = a.
int missingNumber(int* nums, int numsSize)
{
int ret = 0, i = 0;
//先将数组中的数异或在一起
for (i = 0; i < numsSize; i++)
{
ret ^= nums[i];
}
//再将0-numsSize的数异或ret,最后剩下的数就是消失的数字
for (i = 0; i <= numsSize; i++)
{
ret ^= i;
}
return ret;
}
这个思路是,先将0-N个数字的和通过等差数列求和公式相加在一起,再遍历一次数组依次减去数组中的值;
int missingNumber(int* nums, int numsSize)
{
//求0-N的和
int sum = (numsSize + 1) * numsSize / 2;
//减去数组中的值
for (int i = 0; i < numsSize; i++)
{
sum -= nums[i];
}
return sum;
}
题目:给定一个整数数组 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]
我们的思路是,先将整个数组逆置过来,再将需要轮转前k个(前半部分)元素逆置,最后将不需要轮转(后半部分)的元素逆置;这样处理后就是轮转后的数组;
void reverse(int* arr, int len)
{
int k = len - 1;
for (int i = 0; i < k; i++)
{
int tmp = arr[k];
arr[k] = arr[i];
arr[i] = tmp;
k--;
}
}
void rotate(int* nums, int numsSize, int k)
{
//将k的值取模,得到小于等于数组长度的k,避免重复轮转
k %= numsSize;
//逆置整个数组
reverse(nums, numsSize);
//逆置前半部分
int l = k - 1;
for (int i = 0; i < l; i++)
{
int tmp = nums[l];
nums[l] = nums[i];
nums[i] = tmp;
l--;
}
//逆置后半部分
l = numsSize - 1;
for (int i = k; i < l; i++)
{
int tmp = nums[l];
nums[l] = nums[i];
nums[i] = tmp;
l--;
}
}
以上的三逆置写法还可以更简洁:
void reverse(int* arr, int left, int right)
{
for (int i = left; i < right; i++)
{
int tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
right--;
}
}
void rotate(int* nums, int numsSize, int k)
{
//将k的值取模,得到小于等于数组长度的k,避免重复轮转
k %= numsSize;
//逆置整个数组
reverse(nums, 0, numsSize - 1);
//逆置前半部分
reverse(nums, 0, k - 1);
//逆置后半部分
reverse(nums, k, numsSize - 1);
}