Leetcode-面试题17.04.消失的数字
- 异或法
时间复杂度为O(N)
我们的思路是将所有的数异或在一起，然后再将结果异或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等差数列求和再减去数组中的值
时间复杂度为：O(N)
这个思路是，先将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; }
Leetcode-189.轮转数组
题目：给定一个整数数组 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); }
