合并两个有序数组

合并两个有序数组LeetCode88
题目：给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6] 解释：需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] 。
输入：nums1 = [1], m = 1, nums2 = [], n = 0 输出：[1] 解释：需要合并 [1] 和 [] 。 合并结果是 [1] 。

题目看起来很简单，可以用暴力遍历法比较两个数组的大小，定义p和q分别指向两个数组，比较它们当前指向数字大小，由于有向nums1插入数据的需要，这样会导致遍历时出现问题，故使用result存储遍历完之后的数据

  1. var merge = function (nums1, m, nums2, n) {
  2.   const result = [];
  3.   let p = 0, q = 0, cur = 0;
  4.   while (p < m || q < n) {
  5.     if (p === m) {
  6.       result[cur++] = nums2[q++];
  7.     } else if (q === n) {
  8.       result[cur++] = nums1[p++];
  9.     }else if (nums1[p] <= nums2[q]) {
  10.       result[cur++] = nums1[p];
  11.       p++;
  12.     } else if (nums1[p] > nums2[q]) {
  13.       result[cur++] = nums2[q]
  14.       q++;
  15.     }
  16.   }
  17.   result.forEach((item, index) => {
  18.     nums1[index] = item;
  19.   })
  20. };

上面空间复杂度为O(n)，由于nums1的实际长度其实是m+n，所以可以降低空间复杂度，从后往前遍历，那么数据也是从后往前插入，不会影响nums1的遍历，这样就不需要用一个新数组来存储结果了

  1. var merge = function (nums1, m, nums2, n) {
  2.   let p = m-1, q = n-1, cur = 0, tail = m + n -1;
  3.   while (p >= 0 || q >= 0) {
  4.     if (p === -1) {
  5.       cur = nums2[q--];
  6.     } else if (q === -1) {
  7.       cur = nums1[p--];
  8.     } else if (nums1[p] <= nums2[q]) {
  9.       cur = nums2[q--];
  10.     } else if (nums1[p] > nums2[q]) {
  11.       cur = nums1[p--];
  12.     }
  13.     nums1[tail--] = cur;
  14.   }
  15. };

轮转数组

轮转数组LeetCode189
题目：给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4]
输入：nums = [-1,-100,3,99], k = 2 输出：[3,99,-1,-100]

向右轮转k个位置相当于把数组后k个元素平移到数组前面来
方法一：将数组后k个元素剪切并push到数组前面

  1. var rotate = function (nums, k) {
  2.   const length = nums.length;
  3.   const count = k % length;
  5.   nums.unshift(...nums.splice(length - count, count));
  6. };

方法二：将整个数组反转，在对从k开始的左右两个部分数组再次反转，就达到了平移的目的

  1. var rotate = function (nums, k) {
  2.   const reverse = function (arr, left, right) {
  3.     let start = left;
  4.     let end = right;
  5.     while (start < end) {
  6.       const temp = arr[start];
  7.       arr[start++] = arr[end];
  8.       arr[end--] = temp;
  9.     }
  10.   }
  12.   const length = nums.length;
  13.   const count = k % length;
  14.   reverse(nums, 0, length - 1);
  15.   reverse(nums, 0, count - 1);
  16.   reverse(nums, count, length - 1);
  17. };

方法三：以k位的速度不停的交换元素，直到所有的元素都交换一遍（环状替换），从第一个元素开始交换，按照每隔k位开始交换，即第0位交换到第k位，保存第k位原来的值，与第(k+k)%length交换…
交换元素存在两个问题

  • 怎么确定这样交换能交换到每一个元素
  • 交换多少次停止，不设置停止条件会一直交换下去

对于第一个问题，存在两种情况

  • 每次交换的都是不重复的位置，那么交换length次即可满足要求
  • 交换的元素以一定的频率重复，比如长度为6，k为2时，每次都是第0位->第2位->第4位->第0位…重复，这么循环下去，每次交换都是重复的几个元素，所以需要在重复交互之前把元素挪到移动到下一个位置，以下一个位置为起点在进行交换，重复k%length次，就可以完整交互完整个数组了

分析完第一个问题就知道第二个问题的答案了，不管是第一种情况还是第二种情况都只需要交换length次就可满足要求

  1. var rotate = function (nums, k) {
  2.   const length = nums.length;
  3.   if (k % length === 0) return;
  4.   let count = 0;
  5.   let origin = 0;
  6.   let current = 0;
  7.   let temp = nums[current];
  8.   // 分为两种场景，每次交换的都是不重复的位置、交换的元素以一定的频率重复
  9.   // 如果是第二种情况，交换的时候总会回到原点，故需保存原点用作对比
  10.   while (count < length) {
  11.     // 对k取余，元素i的位置需要移到到v位
  12.     current = (current + k) % length;
  13.     const item = nums[current];
  14.     nums[current] = temp;
  15.     temp = item;
  16.     if (current === origin) {
  17.       origin++;
  18.       current = origin;
  19.       temp = nums[current];
  20.     }
  21.     count++;
  22.   }
  23. };