东台做网站哪家便宜,app开发网站排行榜,中国国际室内设计师网,建设工程包括哪几类工程本篇博客讲解LeetCode热题100道普通数组篇中的六道题 第三道#xff1a;轮转数组#xff08;中等#xff09; 第四道#xff1a;除自身以外数组的乘积#xff08;中等#xff09; 第三道#xff1a;轮转数组#xff08;中等#xff09; 方法一#xff1a;使用额外的数… 本篇博客讲解LeetCode热题100道普通数组篇中的六道题 第三道轮转数组中等 第四道除自身以外数组的乘积中等 第三道轮转数组中等 方法一使用额外的数组
class Solution {public void rotate(int[] nums, int k) {int len nums.length;int[] newArr new int[len];for (int i 0; i len; i) {newArr[(i k) % len] nums[i];}System.arraycopy(newArr, 0, nums, 0, len);}
} 1.新建一个nums数组长度的数组。 2.轮转k次。因此我们将从(i k) % len开始将nums数组中的值依次赋值给新数组。 3.最终将新数组中的值拷贝回原来的数组。 时间复杂度 O(n)其中 n 为数组的长度。 空间复杂度 O(n)。 方法二数组翻转
class Solution {public void rotate(int[] nums, int k) {k % nums.length;reverse(nums, 0, nums.length - 1);reverse(nums, 0, k - 1);reverse(nums, k, nums.length - 1);}public void reverse(int[] nums, int start, int end) {while (start end) {int temp nums[start];nums[start] nums[end];nums[end] temp;start 1;end - 1;}}
} 翻转的思想轮转k个位置那么也就相当于先将数组翻转。之后再翻转0k-1这个位置的元素。再翻转kn-1这个位置的元素。下如图演示。 第四道除自身以外数组的乘积中等 方法一前缀之积乘以后缀之积
class Solution {public int[] productExceptSelf(int[] nums) {int length nums.length;// L 和 R 分别表示左右两侧的乘积列表int[] L new int[length];int[] R new int[length];int[] answer new int[length];// L[i] 为索引 i 左侧所有元素的乘积// 对于索引为 0 的元素因为左侧没有元素所以 L[0] 1L[0] 1;for (int i 1; i length; i) {L[i] nums[i - 1] * L[i - 1];}// R[i] 为索引 i 右侧所有元素的乘积// 对于索引为 length-1 的元素因为右侧没有元素所以 R[length-1] 1R[length - 1] 1;for (int i length - 2; i 0; i--) {R[i] nums[i 1] * R[i 1];}// 对于索引 i除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积for (int i 0; i length; i) {answer[i] L[i] * R[i];}return answer;}
}1.新建一两个数组长度为nums的长度。一个L存前缀之积一个R存后缀之积 2.L[i] 表示索引 i 左侧所有元素的乘积因为索引为 0 的元素左侧没有元素 所以 L[0] 1 3.for循环从1开始计算每个元素的前缀之积 L[i] nums[i - 1] * L[i - 1]; 4.再从后往前遍历计算后缀之积。R[length - 1] 1;。R[i] nums[i 1] * R[i 1];得到后缀之积。 5. for (int i 0; i length; i) { answer[i] L[i] * R[i]; } 6.最终返回answer。 时间复杂度O(N)其中 N 指的是数组 nums 的大小。预处理 L 和 R 数组以及最后的遍历计算都是 O(N) 的时间复杂度。空间复杂度O(N)其中 N 指的是数组 nums 的大小。使用了 L 和 R 数组去构造答案L 和 R 数组的长度为数组 nums 的大小 方法二方法一的进阶空间复杂度 O(1) 的方法
class Solution {public int[] productExceptSelf(int[] nums) {int length nums.length;int[] answer new int[length];// answer[i] 表示索引 i 左侧所有元素的乘积// 因为索引为 0 的元素左侧没有元素 所以 answer[0] 1answer[0] 1;for (int i 1; i length; i) {answer[i] nums[i - 1] * answer[i - 1];}// R 为右侧所有元素的乘积// 刚开始右边没有元素所以 R 1int R 1;for (int i length - 1; i 0; i--) {// 对于索引 i左边的乘积为 answer[i]右边的乘积为 Ranswer[i] answer[i] * R;// R 需要包含右边所有的乘积所以计算下一个结果时需要将当前值乘到 R 上R * nums[i];}return answer;}
}1.新建一个answer数组长度为nums的长度。 2.answer[i] 表示索引 i 左侧所有元素的乘积因为索引为 0 的元素左侧没有元素 所以 answer[0] 1 3.for循环从1开始计算每个元素的前缀之积answer[i] nums[i - 1] * answer[i - 1]; 4.再从后往前遍历计算后缀之积。R 为右侧所有元素的乘积。开始R1。从n-1开始遍历。令 answer[i] answer[i] * R;得到最终答案。R * nums[i];得到后缀之积。 5.最终返回answer。 时间复杂度O(N)其中 N 指的是数组 nums 的大小。分析与方法一相同。空间复杂度O(1)输出数组不算进空间复杂度中因此我们只需要常数的空间存放变量。
