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

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

給你一個(gè)數(shù)組，將數(shù)組中的元素向右輪轉(zhuǎn) k 個(gè)位置，其中 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,意味著，每個(gè)元素向后移k位，且長(zhǎng)度n-k~n-1位置的元素會(huì)被挪移至最前方；
• k為非負(fù)整數(shù)，所以，不存在向左輪轉(zhuǎn);

1.3解題思路

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

• 需要輪轉(zhuǎn)k位，即數(shù)組的最后k位會(huì)進(jìn)行挪移至數(shù)組前方，即，當(dāng)我們反轉(zhuǎn)數(shù)組后，可以得知[0,k-1],[k,lenth-1]這兩個(gè)數(shù)組,即為輪轉(zhuǎn)之后的對(duì)應(yīng)數(shù)組，但是，兩個(gè)數(shù)組中的元素排序是反的；
• 接下來(lái)，依次反轉(zhuǎn)[0,k-1],[k,lenth-1]，這兩個(gè)數(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ù)組的長(zhǎng)度。每個(gè)元素被翻轉(zhuǎn)兩次，一共 n 個(gè)元素，因此總時(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]組裝成一個(gè)數(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);

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

總結(jié)

算法的邏輯不同的人有不同的想法，但是殊途同歸，答案是一致的，前提是，一定要靠清楚問(wèn)題，仔細(xì)分析，驗(yàn)證的時(shí)候也要考慮各種情況。

到此這篇關(guān)于javascript算法之?dāng)?shù)組反轉(zhuǎn)的文章就介紹到這了,更多相關(guān)javascript數(shù)組反轉(zhuǎn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論