javascript算法之?dāng)?shù)組反轉(zhuǎn)

更新時(shí)間：2022年08月11日 11:14:09 作者：乾復(fù)道

這篇文章主要介紹了javascript算法之?dāng)?shù)組反轉(zhuǎn)，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下

1.數(shù)組反轉(zhuǎn)

1.1 leecode題目-旋轉(zhuǎn)數(shù)組

給你一個數(shù)組，將數(shù)組中的元素向右輪轉(zhuǎn) k 個位置，其中 k 是非負(fù)數(shù)。

示例：

輸入: nums = [1,2,3,4,5,6,7], k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右輪轉(zhuǎn) 1 步: [7,1,2,3,4,5,6]
向右輪轉(zhuǎn) 2 步: [6,7,1,2,3,4,5]
向右輪轉(zhuǎn) 3 步: [5,6,7,1,2,3,4]

1.2 分析題目

數(shù)組元素有序輪轉(zhuǎn)，即輪轉(zhuǎn)位置k,意味著，每個元素向后移k位，且長度n-k~n-1位置的元素會被挪移至最前方；
k為非負(fù)整數(shù)，所以，不存在向左輪轉(zhuǎn);

1.3解題思路

在不使用額外數(shù)組的前提下，我們可以有如下思考，設(shè)數(shù)組長度為length，則

需要輪轉(zhuǎn)k位，即數(shù)組的最后k位會進(jìn)行挪移至數(shù)組前方，即，當(dāng)我們反轉(zhuǎn)數(shù)組后，可以得知[0,k-1],[k,lenth-1]這兩個數(shù)組,即為輪轉(zhuǎn)之后的對應(yīng)數(shù)組，但是，兩個數(shù)組中的元素排序是反的；
接下來，依次反轉(zhuǎn)[0,k-1],[k,lenth-1]，這兩個數(shù)組，得到的數(shù)組就是答案了

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);

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

1.5 復(fù)雜度分析

時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O(n)，其中 nn 為數(shù)組的長度。每個元素被翻轉(zhuǎn)兩次，一共 n 個元素，因此總時(shí)間復(fù)雜度為 O(2n)=O(n)。
空間復(fù)雜度：O(1)。只需要常數(shù)空間存放若干變量。

1.6 其他解法

思路：

既然輪轉(zhuǎn)k位，即[length-1-k,length-1]位置的元素變?yōu)閇0,k-1]
[0,length-1-k]位置的元素變?yōu)閇length-1-k,length-1]
所以我們只需要將原數(shù)組拆分為[0,k-1]，[length-1-k,length-1]，然后將其按照[length-1-k,length-1]+[0,k-1]組裝成一個數(shù)組即可

代碼：

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);

大家會發(fā)現(xiàn)上述代碼中，我注釋了一行，因?yàn)?，絕對誘人會想使用new Set方法去合并兩個數(shù)組，那么，請注意，千萬不能使用，因?yàn)?，new Set方法，會講兩個數(shù)組進(jìn)行合并后去重，如果原數(shù)組中出現(xiàn)相同元素，則，new Set將會給使用者狠狠上一課！