JavaScriptデータ構造とアルゴリズム-Sort-(leetcode原題)

8858 ワード

javascript アルゴリズム並べ替え先端

元のブログアドレス:https://finget.github.io/2019...
並べ替え

時間複雑度(運転回数)

コンピュータが基本コードの行を実行するには、演算を行う必要があると仮定します.

int aFunc(void) {
    printf("Hello, World!
");      //       1  
    return 0;       //      1  
}

以上の方法は2回演算します.

int aFunc(int n) {
    for(int i = 0; i

この方法は(n＋1＋n＋1)＝2 n＋2次演算を必要とする.アルゴリズムに必要な演算回数を入力サイズnの関数で表します.すなわちT(n)です.
一般的なアルゴリズムの時間の複雑さ:

O(1)定数タイプ

O(n)リニア

O(n^2)二乗型

O(n^3)立方型

O(2^n)指数型

O(log 2^n)対数形

O(nlog 2^n)二次元タイプ

時間の複雑さの分析方法:1、時間の複雑さは、関数の基本的な操作で実行される回数の2、一般的なデフォルトは最悪の時間の複雑さである.つまり、分析が最悪の場合に実行できる回数の3、定数の項目を無視して4、運転時間の増加傾向に注目して、関数式の中で最も速い表現を増加させ、係数5、係数を無視している.計算時間の複雑さは、nの増加関数の実行回数に伴う増加傾向を推定する6、再帰的アルゴリズムの時間的複雑さは、再帰的な合計回数＊再帰的な基本動作毎に実行される回数である.

空間複雑度(占有メモリ)

アルゴリズムによって消費される空間

一つのアルゴリズムの占有空間とは、アルゴリズムが実際に占有する補助空間の合計である.

アルゴリズムの空間複雑度アルゴリズムの空間複雑度は、実際に占有された空間を計算するのではなく、アルゴリズム全体の「補助空間ユニットの個数」を計算する.アルゴリズムの空間複雑度S(n)は、問題規模nの関数であるこのアルゴリズムによって消費される空間の数レベルとして定義される.記録:

S(n)=O(f(n)1
アルゴリズム実行時に必要な補助空間が入力データ量nに対して定数である場合、このアルゴリズムの補助空間はO(1)と呼ばれます.再帰的アルゴリズムの空間複雑度:再帰的深さN＊再帰的に必要な補助空間は、再帰的に必要な補助空間が定数である場合、再帰的な空間複雑度はO(N)である.
泡の並べ替え
原理:最初の元素から、これから比較して、自分の小さい元素に出会ったら、位置を交換します.

let arr = [89, 19, 90, 9, 3, 21, 5, 77, 10, 22]

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
  }
  return arr;
}
bubbleSort(arr)

for (let j = 0; j < arr.length - 1 - i; j++)は、ここの理解について:

i = 0の時、jの最大値はarr.length-2です.最後の値は違いますか?いいえ、if (arr[j] > arr[j + 1])はj,j+1ならあふれます.

はどうしてまた-iですか?i=0を  すると、   は  の  の  に かれます.このとき、  の  を うときにi=1は  の   はこれ   べる  がありません.これに べると、length-1-1 となります.    を らすことができます.    の  さを らすことができます.したがって、j < arr.length - 1 - i.

//      
let arr = [89, 19, 90, 9, 3, 21, 5, 77, 10, 22]

function bubbleSort(arr) {
//  i       
  for (let i = arr.length - 1 ; i > 0 ; i--) {
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
  }
  return arr;
}
bubbleSort(arr)

 べ えを  
その  の  は の りです.  に、 べ えられていないシーケンスの で  ( )  を つけて、 べ えられたシーケンスの    に  します.その 、 りの べ えられていない  の から  ( )  を し けて、 べ えられたシーケンスの  に きます.この  によって、すべての  がソートされるまで.let arr = [89, 19, 90, 9, 3, 21, 5, 77, 10, 22]
function selectionSort(arr) {
  let len = arr.length;
  let min = ''; //       
  // i < len-1 *   j = i + 1,             
  for (let i = 0 ; i < len-1 ; i++) {
      min = i
    for (let j = i+1; j < len; j++) {
      if (arr[min] > arr[j]) {
        min = j
      }
    }
    [arr[i], arr[min]] = [arr[min], arr[i]]
    console.log(`i=${i}; min=${min}; arr=${arr}`)
  }
  return arr;
}
selectionSort(arr)
//     
i=0; min=4; arr=3,19,90,9,89,21,5,77,10,22
i=1; min=6; arr=3,5,90,9,89,21,19,77,10,22
i=2; min=3; arr=3,5,9,90,89,21,19,77,10,22
i=3; min=8; arr=3,5,9,10,89,21,19,77,90,22
i=4; min=6; arr=3,5,9,10,19,21,89,77,90,22
i=5; min=5; arr=3,5,9,10,19,21,89,77,90,22
i=6; min=9; arr=3,5,9,10,19,21,22,77,90,89
i=7; min=7; arr=3,5,9,10,19,21,22,77,90,89
i=8; min=9; arr=3,5,9,10,19,21,22,77,89,90
             ，         ，           。

           2，    0。

   1:

  : [3,6,9,1]
  : 3
  :         [1,3,6,9],        (3,6)   (6,9)           3。
   2:

  : [10]
  : 0
  :          2，     0。
  :

                  ，     32          。
                          。
var maximumGap = function(nums) {
    //if (nums.length < 2) {
        //return 0;
  //  }
    //nums.sort((a,b) =>  a-b)
    //let max = 0;
    //for(let i = 0; i< nums.length-1; i++) {
        //max = nums[i+1]-nums[i]>max?nums[i+1]-nums[i]:max
    //}
    //return max;
    if (nums.length < 2) {
        return 0;
    }
    nums.sort((a,b) =>  a-b)
    let max = 0,grap;
    for(let i = 0; i< nums.length-1; i++) {
        grap = nums[i+1]-nums[i]
        max = grap>max?grap:max
    }
    return max;
};
// leetcode    
/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumGap = function (nums) {
  if (nums.length < 2) return 0
  let max = nums[0], min = nums[0]
  for (let i = 1; i < nums.length; i++) {
    max = Math.max(nums[i], max)
    min = Math.min(nums[i], min)
  }
  let delta = (max - min) / (nums.length - 1)
  let maxBucket = new Array(nums.length - 1).fill(Number.MIN_SAFE_INTEGER)
  let minBucket = new Array(nums.length - 1).fill(Number.MAX_SAFE_INTEGER)
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] == min || nums[i] == max) continue
    let index = Math.floor((nums[i] - min) / delta)
    maxBucket[index] = Math.max(maxBucket[index], nums[i])
    minBucket[index] = Math.min(minBucket[index], nums[i])
  }
  let prev = min, maxGap = 0
  for (let i = 0; i < minBucket.length; i++) {
    if (minBucket[i] == Number.MAX_SAFE_INTEGER) continue
    maxGap = Math.max(minBucket[i] - prev, maxGap)
    prev = maxBucket[i]
  }
  maxGap = Math.max(max - prev, maxGap)
  return maxGap
};

//    [3,6,9,1]
//     9，    1
//     [-∞,-∞,-∞]      ，       1
//     [+∞,+∞,+∞]      ，       1
//       (9-1)/4 = 2
//         (nums[i]-   )/    
// (3 - 1)/2 = 1 ，       1 3， [+∞,3,+∞]，      [-∞,3,-∞]
// (6 - 1)/2 = 2.5 = 2，     [+∞,3,6]     [-∞,3,6]
// 9     ，  
// 1     ，  
//                   ，       ，            
//                  =1，    [+∞,3,6]，   [-∞,3,6]    =9
//       3 ，1-3(   )，3(   )-6(   )，6(   )-9
//    2,3,3     3
パリティで  を べ える           A，      ，     ， A                  。

                   。

 

  ：

  ：[3,1,2,4]
  ：[2,4,3,1]
   [4,2,3,1]，[2,4,1,3]   [4,2,1,3]      。
 

  ：

1 <= A.length <= 5000
0 <= A[i] <= 5000
var sortArrayByParity = function(A) {
    let arr = []
    for(let i = 0;i
パリティ   II           A， A         ，       。

       ，    A[i]     ，i     ；  A[i]     ， i     。

                    。

  ：

  ：[4,2,5,7]
  ：[4,5,2,7]
  ：[4,7,2,5]，[2,5,4,7]，[2,7,4,5]      。
 

  ：

2 <= A.length <= 20000
A.length % 2 == 0
0 <= A[i] <= 1000
 え :ダブルポインタを って、  +2var sortArrayByParityII = function(A) {
    let i = 0;
    let j = 1;
    while (j < A.length && i < A.length) {
        if (A[i] % 2 == 0) {
            i += 2;
        } else {
            while (A[j] % 2 != 0 && j < A.length) {
                j += 2;
            }
            if (j < A.length) {
                let tmp = A[i]
                A[i] = A[j]
                A[j] = tmp
            }
        }
    }
    return A;
};
  の  がありません.            ，               。

   1:

  : [1,2,0]
  : 3
   2:

  : [3,4,-1,1]
  : 2
   3:

  : [7,8,9,11,12]
  : 1
  :

            O(n)，             。
//      
function firstMissingPositive(arr) {
    //       
    arr = arr.filter(item => item > 0);

    if(arr.length ==0) {
        //           ，        1
        return 1;
    } else {
        //   
        arr.sort((a,b) => a-b);
        //        1，    1
        if(arr[0] !== 1) {
            return 1
        } else {
            for (let i = 0,len = arr.length; i < len; i++) {
                if(arr[i+1] - arr[i] > 1) {
                    return arr[i] + 1
                } 
            }
            //       return，           + 1
            return arr.pop() + 1
        }
    }
};
//             ,      ，                  
function firstMissingPositive(arr) {
    arr = arr.filter(item => item > 0);

    //     ，      ，         1   1
    let min = 0;
    let len = arr.length;
    for (let i = 0; i < len; i++) {
        min = i;
        for (let j = i+1; j < len; j++) {
            if (arr[min] > arr[j]) {
                min = j
            }
        }
        [arr[i], arr[min]] = [arr[min], arr[i]]
        //           ，      
        if (i>0) {
            if(arr[i]-arr[i-1]>1) {
                return arr[i-1] + 1
            }
        } else {
            //            1，   1 
            if (arr[0]!==1){
                return 1;
            }
        }
    }
    //          ，        ，           0   1，          +1
    return arr.length?arr.pop() + 1:1
}
  に
    グループを って、  のある  を  に てください.

Javascriptの配列と配列の方法