LeetCode Hot 100 第7天
1. 189 轮转数组（规律）
链接：题目链接
题解：
题解
时间复杂度O(n)：
k = n * len + x (len等于数组长度)，n * len 可以忽略掉（将数组向右轮转n * len次，数组不会发生任何变化），所以真正需要处理的轮转次数 x = k % len- 数组像右轮转x次 = 尾部x个元素移动到数组头部 + 其余元素向右移动
- 尾部x个元素移动到数组头部：先将数组反转，再将[0, x - 1]下标元素反转
- 其余元素向右移动：先将数组反转，再将[x, len - 1]下标元素反转
代码：
class Solution {public void rotate(int[] nums, int k) {int len = nums.length;k = k % len;swapRange(nums, 0, len - 1);swapRange(nums, 0, k - 1);swapRange(nums, k, len - 1);}private void swapRange(int[] nums, int l, int r) {while(l < r) {int temp = nums[l];nums[l] = nums[r];nums[r] = temp;l ++;r --;}}
}
2. 238 除自身以外数组的乘积（公式 + 规律）
链接：题目链接
题解：
题解
时间复杂度O(n)：
answer[i] = nums 中除 nums[i] 之外其余各元素的乘积 = 所有乘积 / nums[i]（nums[i]=0的情况需要特殊讨论）- 遍历数组维护所有元素的乘积
- 注意：当nums[i]=0 && 0的个数>1时，answer数组都是0
- 注意：当nums[i]=0 && 0的个数=1时，answer[i] = 非0数的乘积，answer[j] = 0 (j != i)
- 其他情况参考1
代码：
class Solution {public int[] productExceptSelf(int[] nums) {// 0的个数 个数 > 1 直接返回0数组 个数 == 0 乘积不算0 记录0下标 个数 == 0 直接算0下标int len = nums.length;int zeroCount = 0;int zeroIndex = -1;int allMultiplicationResult= 1;for (int i = 0; i < len; ++ i) {if (nums[i] == 0) {zeroCount ++;zeroIndex = i;} else {allMultiplicationResult *= nums[i];}}int[] ans = new int[len];if (zeroCount > 1) {return ans;} if (zeroCount == 1) {ans[zeroIndex] = allMultiplicationResult;return ans;}for (int i = 0; i < len; ++ i) {ans[i] = allMultiplicationResult / nums[i];}return ans;}
}
3. 41 缺失的第一个正数（规律 + hash）
链接：题目链接
题解：
题解
时间复杂度O(n)：
- 当nums数组长度为n时，缺失的最小整数的最大值是n+1，例如最极端的情况[1, 2, 3] 那么确缺失的最小整数 = 4
- 从1遍历至n，hash存储出现过的值，如果i值 不存在hash中，那么就是缺失的最小整数
- 题目要求时间复杂度为O(1)常数级别，那么只能把hash存储在nums数组中体现
- nums[i] <= 0的情况元素无效，那么等值替换为n + 1（即最大可能取到的值）
- 因为答案存在[1, n + 1]，那么我们把i值映射在i-1下标元素上，用负数表示已存在（负数不会影响nums的绝对值）
- 遍历元素，做完hash映射时，再遍历一遍数组，如果nums[i] > 0（没被hash标记），那么缺失的最小整数就是i +1
- 遍历元素，数组都被标记时（nums[i] <= 0），那么缺失的最小整数就是n + 1
代码：
class Solution {public int firstMissingPositive(int[] nums) {int len = nums.length;for (int i = 0; i < len; ++ i) {if (nums[i] <= 0) {nums[i] = len + 1;}}for (int i = 0; i < len; ++ i) {int absNum = Math.abs(nums[i]);if (absNum <= len) {nums[absNum - 1] = -1 * Math.abs(nums[absNum - 1]);}}for (int i = 0; i < len; ++ i) {if (nums[i] > 0) {return i + 1;}}return len + 1;}
}
如果对你有帮助，辛苦点个赞，谢谢啦，朋友！！！