JS配列の重み付け方法のまとめ/テーマ

5130 ワード

1、長さn-1の配列があって、1-nの中で繰り返しない乱序の数を含んで、範囲内で配列の中にない数を探して、空間の占有、性能の最適化、オーバーフローなどの情況を考慮して、少なくとも2つのアルゴリズムを書きます
nがあまり大きくない場合,和を求めることが考えられる.まず1~nのすべての数の和を算出し,次に配列に現れるすべての自然数の和を減算する.時間的複雑度はO(n),空間的複雑度はO(1)であった.この方法の欠点は,nがあまり大きくできず,nが比較的大きい場合,和があふれやすいことである.
ビットマップを使う.配列全体を最初から最後までスキャンし,出現数に応じたビットを1に設定.次にビットマップをスキャンし、1ではないビットを見つけます.つまり、探している数です.この方法の時間的複雑度はO(n),空間的複雑度はO(n)であった.
異或には巧みなところがある:同じ変数とその変数と別の変数の異或値の異或はこの変数自身に等しい.だから私たちは1~nのすべての数を異にして、配列の中で現れたすべての数を異にして、それからこの2つの異種の結果を異にして、最後に得た値は私たちが探している値です.このように時間的複雑度はO(n),空間的複雑度はO(1)である.第2の方法よりも空間的に優れており、第1の方法でいうオーバーフロー問題は発生しない.
解法一:配列の和を求める
 var arr = [9, 5, 7, 8, 6, 3, 4, 1]
    var sum = 0; //    
    var sum1 = 0; //    

    var find = function() {
        for (var i = 0; i < arr.length; i++) {
            sum += parseInt(arr[i]);
        };
        for (var i = 1; i <= arr.length + 1; i++) {
            sum1 += i;
        };
        var wow = sum1 - sum;
        console.log(wow);
        console.log(sum1);
        console.log(sum);
    };
    find();

配列の重み付け方法のまとめ


二層サイクル、外層サイクル要素、内層サイクル時の比較値.同じ値がある場合はスキップし、異なる場合はpushが配列に入ります.
このときのスキップは内層ループから飛び出すのではなく、内層比較が重複している場合は現在の要素を無視し、次の要素にジャンプしてループ比較を行います.
Array.prototype.distinct = function(){
    var arr = this,
     result = [],
    for(let i = 0; i < arr.length; i++){
     for(let j = i + 1; j < arr.length; j++){
      if(arr[i] === arr[j]){
       j = ++i;
      }
     }
     result.push(arr[i]);
    }
    return result;
   }
   var arra = [1,2,3,4,4,1,1,2,1,1,1];
   arra.distinct();    //  [3,4,2,1]

i++と++iはまた区別がつかなくなった
let i=1;
let a=0;
  i++          a=i++ =>  a=i, i=i+1   =>  a===1;
  ++i          a=++i =>  i=i+1 , a=i   =>  a===2;

クリアの原理を説明して、簡単な配列を例にします.
function distinct(){
   var arr = [1,2,2,1,3];
    result = [];
    for(let i = 0; i < arr.length; i++){
     for(let j = i + 1; j < arr.length; j++){
      if(arr[i] === arr[j]){
        console.log('     j- ',j);
         j = ++i;
         console.log('     j',j);
         console.log('     i',i);
      }
     }
     console.log('     i',i);
     result.push(arr[i]);
    }
    document.getElementById("shuzuquchong").innerHTML=result;
    return result;
   };
//      
//       j-  3
//       j 1
//       i 1
//       j-  2
//       j 2
//       i 2
//       i 2
//       i 3
//       i 4

方法2:spliceを利用して直接元の配列で操作する
二層サイクル、外層サイクル要素、内層サイクル時の比較値;値が同じであれば、この値(後(前と重複)の値を削除します.注意点:要素を削除した後、配列の長さも1を減らす必要があります.
function distinct(){
    var a = [1,2,3,4,5,6,5,3,2,4,56,4,1,2,1,1,1,1,1,1,];
   for(let i = 0; i < a.length; i++){
   for(let j = i + 1; j < a.length; j++){
   if(a[i] == a[j]){
    a.splice(j,1);  //splice()    /      /    ,          。          。
    a.length--;
    j--;
   }
  }
 }
 document.getElementById("shuzuquchong").innerHTML=a;
    return a;
};

splice()メソッドとslice()メソッドを区別します
arrayObject.splice(index,howmany,item1,.....,itemX)    :          。

splice()メソッドは、配列からアイテムを追加/削除し、削除されたアイテムを返します.
ndex
必要です.整数で、アイテムを追加/削除する場所を指定し、負数を使用して配列の最後から位置を指定します.
howmany
必要です.削除するアイテムの数.0に設定した場合、アイテムは削除されません.
item1, ..., itemX
オプション.配列に追加された新しいアイテム.
arrayObject.slice(start,end)  slice()                  。

start
必要です.選択を開始する場所を指定します.負数の場合、配列の末尾から算出される位置を規定します.すなわち、−1は最後の要素を指し、−2は最後から2番目の要素を指し、このように推定される.
end
オプション.選択を終了する場所を指定します.このパラメータは、配列フラグメントの終端にある配列の下付きです.このパラメータが指定されていない場合、分割された配列にはstartから配列終了までのすべての要素が含まれます.このパラメータが負の場合、配列の末尾から計算される要素を規定します.
方法3:オブジェクトの属性が同じではない特徴を利用して重み付けを行う
オブジェクトのプロパティは同じではありません.
   function distinct(){
    var arr = [1,2,3,4,5,6,5,3,2,4,56,4,1,2,1,1,1,1,1,1,];
        obj = {},
        result = [];
   for(let i = 0; i< arr.length; i++){
       if(!obj[arr[i]]){ //      ,         
        console.log('obj[arr[i]]',obj[arr[i]]);
        obj[arr[i]] = 1;
         result.push(arr[i]);
  }
 }
 document.getElementById("shuzuquchong").innerHTML=result;
 return result;
};

方法4:配列の再帰的な重み付け
再帰的な思想を運用する
最初にソートし、最後から比較し、同じ場合は削除します.
再帰とは
では、再帰とは何でしょうか.再帰を理解するには、まず再帰とは何かを理解しなければならないが、実際にはこの言葉は再帰である.このように言うのは理解しにくいかもしれませんが、次に簡単な例を挙げてこの話の意味を説明します.
もし私たちが今何が再帰なのか分からないとしたら、私たちは自然にブラウザを開けて、グーグルのホームページに入力したいと思っています.私たちは検索をクリックして再帰して、それから私たちはウィキペディアの中で再帰の基本的な定義を知っています.再帰が実際にスタックと関係があることを知ったとき、あなたはまた隠しました.スタックとは何ですか.データ構造がはっきりしていないので、この時、あなたはまたグーグルを開いて、スタックを検索するしかありません.次に、メモリ/オペレーティングシステムを順に理解します.基本的に知識を理解した後、オペレーティングシステムを通じてメモリを理解し、メモリを通じてスタックを理解し、スタックを通じて何が再帰的なのかを理解しました.これが再帰だったのか.
これで少しわかるでしょうが、この過程は実は再帰の過程で、再帰を理解していないならば、まず何が再帰なのかを理解して、あなたはこれが循環で再帰ではないと言うかもしれませんが、私たちは前に言って、再帰は終了条件が必要で、それではあなたは再帰が何なのかが実は終了条件であることを理解します.検索エンジンは再帰関数として機能する(イメージの仮定にすぎない).再帰/スタック/メモリ/オペレーティングシステムを順番に検索するプロセスは、前の段階であり、すべてのことを理解した後、意味を理解するプロセスは戻る段階です.
再帰とループの違いは、ループはコードを実行し、パラメータが異なるだけである.再帰は自分に呼び出されます.例えば、循環は同じ場所を回っているようなものです.再帰は1階1階に入って、元の道に戻って、各階は同じですが.