快捷導(dǎo)航

TypeScript調(diào)整數(shù)組元素順序算法

更新時(shí)間：2022年04月19日 11:11:39 作者：神奇的程序員

數(shù)組類型在TS中可以使用多種方式,比較靈活,下面這篇文章主要給大家介紹了關(guān)于TypeScript調(diào)整數(shù)組元素順序算法的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下

前言

有一個(gè)整數(shù)數(shù)組，我們想按照特定規(guī)則對(duì)數(shù)組中的元素進(jìn)行排序，比如：數(shù)組中的所有奇數(shù)位于數(shù)組的前半部分。

本文將帶大家實(shí)現(xiàn)這個(gè)算法，歡迎各位感興趣的開(kāi)發(fā)者閱讀本文。

實(shí)現(xiàn)思路

我們通過(guò)一個(gè)實(shí)例來(lái)分析下：假設(shè)有這樣一個(gè)數(shù)組：[2, 4, 5, 6, 7, 8, 9, 11]，將奇數(shù)移動(dòng)到最前面后，就是：[11, 9, 5, 7, 6, 8, 4, 2]。

通過(guò)觀察后，我們發(fā)現(xiàn)在掃描這個(gè)數(shù)組的時(shí)候，如果發(fā)現(xiàn)有偶數(shù)出現(xiàn)在奇數(shù)的前面，就交換他們的順序，交換之后就符合要求了。

因此，我們可以維護(hù)兩個(gè)指針：

第一個(gè)指針初始化時(shí)指向數(shù)組的第一個(gè)數(shù)字，它只向后移動(dòng)；
第二個(gè)指針初始化時(shí)指向數(shù)組的最后一個(gè)數(shù)字，它只向前移動(dòng)；

在兩個(gè)指針相遇之前，第一個(gè)指針總是位于第二個(gè)指針的前面。如果第一個(gè)指針指向的數(shù)字是偶數(shù)，并且第二個(gè)指針指向的數(shù)字是奇數(shù)，則交換這兩個(gè)數(shù)字。

接下來(lái)，我們來(lái)通過(guò)圖來(lái)描述下上述例子交換指針的過(guò)程，如下所示：

第一個(gè)指針永遠(yuǎn)指向偶數(shù)，如果不為偶數(shù)就向后移動(dòng)；
第二個(gè)指針永遠(yuǎn)指向奇數(shù)，如果不為奇數(shù)就向前移動(dòng)；
當(dāng)兩個(gè)指針各自指向的數(shù)都符合條件時(shí)，就交換兩個(gè)元素的位置；
交換完成后，重復(fù)上述步驟，直至兩個(gè)指針相遇或者第一個(gè)指針位于第二個(gè)指針之后則代表問(wèn)題已得到解決。

實(shí)現(xiàn)代碼

有了思路之后，我們來(lái)看下實(shí)現(xiàn)代碼，如下所示：

export class AdjustArrayOrder {
  // 指向數(shù)組元素的兩個(gè)指針：一個(gè)指向數(shù)組頭部、一個(gè)指向數(shù)組尾部
  private begin = 0;
  private end = 0;

  // 調(diào)整數(shù)組中奇數(shù)與偶數(shù)元素的位置：奇數(shù)位于偶數(shù)前面
  reorderOddEven(arr: Array<number>): void {
    this.end = arr.length - 1;
    while (this.begin < this.end) {
      // 向后移動(dòng)begin(轉(zhuǎn)成二進(jìn)制跟1做與運(yùn)算，運(yùn)算結(jié)果為0就表示為偶數(shù))，直至其指向偶數(shù)
      while (this.begin < this.end && (arr[this.begin] & 0x1) !== 0) {
        this.begin++;
      }

      // 向前移動(dòng)end（轉(zhuǎn)成二進(jìn)制跟1做與運(yùn)算，運(yùn)算結(jié)果為1就表示為奇數(shù)），直至其指向奇數(shù)
      while (this.begin < this.end && (arr[this.end] & 0x1) === 0) {
        this.end--;
      }

      // begin指向了偶數(shù)，end指向了奇數(shù)
      if (this.begin < this.end) {
        // 交換兩個(gè)元素的順序
        [arr[this.begin], arr[this.end]] = [arr[this.end], arr[this.begin]];
      }
    }
    // 重置指針位置
    this.begin = 0;
    this.end = 0;
  }
}

代碼的可擴(kuò)展性

如果數(shù)組中的元素不按照奇前偶后排列，我們需要將其按照大小進(jìn)行劃分，所有負(fù)數(shù)都排在非負(fù)數(shù)的前面，應(yīng)該怎么做？

聰明的開(kāi)發(fā)者可能已經(jīng)想到了方案：雙指針的思路還是不變，我們只需修改內(nèi)層while循環(huán)的的判斷條件即可。

這樣回答沒(méi)有問(wèn)題，確實(shí)解決了這個(gè)問(wèn)題，那么如果再改改題目，我們需要把數(shù)組中的元素分為兩部分，能被3整除的數(shù)都在不能被3整除的數(shù)前面，應(yīng)該怎么做？

經(jīng)過(guò)思考后，我們發(fā)現(xiàn)這個(gè)問(wèn)題無(wú)論再怎么改變都有一個(gè)共同的部分：雙指針的邏輯永遠(yuǎn)不會(huì)變。變化的只是判斷條件，那么我們就可以把變化的部分提取成函數(shù)，當(dāng)作參數(shù)讓調(diào)用者傳進(jìn)來(lái)，這樣就完美的解決了這個(gè)問(wèn)題，也正是我們所提及的代碼的可擴(kuò)展性。

最后，我們來(lái)看下實(shí)現(xiàn)代碼，如下所示：

  // 元素排序
  reorder(arr: Array<number>, checkFun: (checkVal: number) => boolean): void {
    this.end = arr.length - 1;
    while (this.begin < this.end) {
      // 向后移動(dòng)begin
      while (this.begin < this.end && !checkFun(arr[this.begin])) {
        this.begin++;
      }

      // 向前移動(dòng)end
      while (this.begin < this.end && checkFun(arr[this.end])) {
        this.end--;
      }

      // begin與end都指向了正確的位置
      if (this.begin < this.end) {
        // 交換兩個(gè)元素的順序
        [arr[this.begin], arr[this.end]] = [arr[this.end], arr[this.begin]];
      }
    }

測(cè)試用例

我們先來(lái)測(cè)試下奇數(shù)在偶數(shù)之前的函數(shù)處理代碼能否正常執(zhí)行，如下所示：

const adjustArrayOrder = new AdjustArrayOrder();
// 奇數(shù)在前
const arr = [2, 4, 5, 6, 7, 8, 9, 11];
adjustArrayOrder.reorderOddEven(arr);
console.log(arr);

執(zhí)行結(jié)果如下所示：

最后，我們來(lái)測(cè)試下reorder函數(shù)能否正常執(zhí)行：

負(fù)數(shù)在數(shù)組的最前面

// 負(fù)數(shù)在前
const checkMinusNumber = function (val: number) {
  return val > 0;
};
const arr = [2, 4, 5, 6, 7, -8, -10 - 12, -2];
adjustArrayOrder.reorder(arr, checkMinusNumber);
console.log(arr);

能被3整除的數(shù)在數(shù)組的最前面

const checkDivisible = function (val: number) {
  return val % 3 !== 0;
};
const arr = [2, 4, 5, 6, 3, 6, 9, 12];
adjustArrayOrder.reorder(arr, checkDivisible);
console.log(arr);