​
​

活动地址：CSDN21天学习挑战赛

前言

OK，今天是一个简单的应用题材分析，算法的学习需要我们不断的去思考，今天的题目依然来自leecode。

1.数组反转

1.1 leecode题目-旋转数组

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例：
输入: 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]
1
2
3
4
5
6
7

1.2 分析题目

• 数组元素有序轮转，即轮转位置k,意味着，每个元素向后移k位，且长度n-k~n-1位置的元素会被挪移至最前方；
• k为非负整数，所以，不存在向左轮转;

1.3解题思路

在不使用额外数组的前提下，我们可以有如下思考，
设数组长度为length，则

• 需要轮转k位，即数组的最后k位会进行挪移至数组前方，即，当我们反转数组后，可以得知[0,k-1],[k,lenth-1]这两个数组,即为轮转之后的对应数组，但是，两个数组中的元素排序是反的；
• 接下来，依次反转[0,k-1],[k,lenth-1]，这两个数组，得到的数组就是答案了

1.4 代码

const reverseArray = (nums, start, end) => {
  while (start < end) {
    const temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
    start += 1;
    end -= 1;
  }
  return nums;
};

var reverseFunction = function(nums, k) {
  let length  = nums.length;
  nums = reverseArray(nums, 0, length - 1);
  nums = reverseArray(nums, 0, k - 1);
  nums = reverseArray(nums, k, length - 1);
};

reverseFunction([1,2,3,4,5,6,7],3);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

输出：[5,6,7,1,2,3,4]

1.5 复杂度分析

• 时间复杂度：时间复杂度：O(n)，其中 nn 为数组的长度。每个元素被翻转两次，一共 n 个元素，因此总时间复杂度为 O(2n)=O(n)。
• 空间复杂度：O(1)。只需要常数空间存放若干变量。

1.6 其他解法

• 思路：

  • 既然轮转k位，即[length-1-k,length-1]位置的元素变为[0,k-1]
  • [0,length-1-k]位置的元素变为[length-1-k,length-1]
  • 所以我们只需要将原数组拆分为[0,k-1]，[length-1-k,length-1]，然后将其按照[length-1-k,length-1]+[0,k-1]组装成一个数组即可

• 代码

var reverseFunction2 = function(nums, k) {
  let length  = nums.length;
  let arrayLeft = nums.slice(0,length-k);
  let arrayRight = nums.slice(length-k);
  // return [...new Set([...arrayRight,...arrayLeft])];
  return arrayRight.concat(arrayLeft);
};
reverseFunction2([1,2,3,4,5,6,7],3);
1
2
3
4
5
6
7
8

大家会发现上述代码中，我注释了一行，因为，绝对诱人会想使用new Set方法去合并两个数组，那么，请注意，千万不能使用，因为，new Set方法，会讲两个数组进行合并后去重，如果原数组中出现相同元素，则，new Set将会给使用者狠狠上一课！

总结

算法的逻辑不同的人有不同的想法，但是殊途同归，答案是一致的，前提是，一定要靠清楚问题，仔细分析，验证的时候也要考虑各种情况。

寄语

算法的验证，必要且一定，好的算法，少不了单元测试