データ構造とアルゴリズム: 奇数偶数による配列のソート II

[[429517]]

簡単なシミュレーション問題、ぜひ挑戦してみてください！

配列を偶数/奇数でソートする II

LeetCode の問題へのリンク: https://leetcode-cn.com/problems/sort-array-by-parity-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 層の for ループと、使用された要素を表すために使用される配列である可能性があります。この計算時間は O(n^2) です。

方法1

実際、この問題は非常に簡単な方法で解決でき、時間の計算量は O(n) です。C++ コードは次のとおりです。

クラスソリューション{
公共：
    ベクトル< int > sortArrayByParityII(ベクトル< int >& A) {
        vector< int > even(A. size () / 2); // オーバーヘッドを節約するために配列サイズを初期化します
        ベクトル< int > 奇数(A.size ( ) / 2);
        ベクトル< int > 結果(A.size ( ));
偶数インデックス = 0;
整数奇数インデックス = 0;
結果インデックス= 0;
        // 配列Aを偶数配列と奇数配列に入れる
( int i = 0; i < A.size ( ); i++) {
            A[i] % 2 == 0の場合、even[evenIndex++] = A[i];
そうでない場合、 odd[oddIndex++] = A[i];
        }
        // 偶数配列と奇数配列をそれぞれ結果配列に格納します
( int i = 0; i < evenIndex; i++) {
            結果[resultIndex++] = even[i];
            結果[結果インデックス++] = 奇数[i];
        }
結果を返します。
    }
 };

• 時間計算量: O(n)
• 空間計算量: O(n)

方法2

上記のコードでは、2 つの補助配列を構築しており、配列 A は 2 回のトラバースに相当します。補助配列を使用する利点は、アイデアが明確であることです。最適化は、これらの 2 つの補助ツリーを使用しないことです。コードは次のとおりです。

クラスソリューション{
公共：
    ベクトル< int > sortArrayByParityII(ベクトル< int >& A) {
        ベクトル< int > 結果(A.size ( ));
 int evenIndex = 0; // 偶数テーブル
int oddIndex = 1; // 奇数テーブル
( int i = 0; i < A.size ( ); i++) {
            もし(A[i]%2==0)であれば
                結果[evenIndex] = A[i];
                偶数インデックス += 2;
            }
それ以外{
                結果[奇数インデックス] = A[i];
                奇数インデックス += 2;
            }
        }
結果を返します。
    }
 };

• 時間計算量 O(n)
• 空間計算量 O(n)

方法3

もちろん、元の配列を変更することもできますし、結果の配列も必要ありません。

クラスソリューション{
公共：
    ベクトル< int > sortArrayByParityII(ベクトル< int >& A) {
整数奇数インデックス = 1;
 ( int i = 0; i < A.size ( ); i += 2) {
            if (A[i] % 2 == 1) { // 偶数位置に奇数が発生した
                while(A[oddIndex] % 2 != 0) oddIndex += 2; // 奇数の位置にある偶数を見つける
                swap(A[i], A[oddIndex]); // 置換
            }
        }
 Aを返します。
    }
 };

• 時間計算量: O(n)
• 空間計算量: O(1)

ここでの時間計算量は O(n^2) ではありません。偶数ビットと奇数ビットの両方が 1 回だけ操作され、関係は n/2 * n/2 ではなく、n/2 + n/2 だからです。

その他の言語

ジャワ

// 方法 1
クラスソリューション{
公共  int [] sortArrayByParityII( int [] 数値) {
        // 奇数と偶数をそれぞれnumsに格納します
int len ​​= nums.length;
偶数インデックス = 0;
整数奇数インデックス = 0;
 int [] even = 新しいint [len / 2];
 int [] odd = 新しいint [len / 2];
 ( int i = 0; i < len; i++)の場合{
            （数値[i] % 2 == 0）の場合{
                偶数[evenIndex++] = nums[i];
            }それ以外{
                奇数[oddIndex++] = nums[i];
            }
        }
        // パリティ配列をnumsに格納します
整数 インデックス= 0;
 ( int i = 0; i < even.length; i++) {
            nums[インデックス++] = even[i];
            nums[インデックス++] = odd[i];
        }
数値を返します。
    }
 }

Python3

 #方法2
クラスソリューション:
    def sortArrayByParityII(self, nums: List[ int ]) -> List[ int ]:
        結果 = [0]*len(数値)
        偶数インデックス = 0
        奇数インデックス = 1
 i が範囲(len(nums))内にある場合:
            if nums[i] % 2: #奇数
                結果[奇数インデックス] = 数値[i]
                奇数インデックス += 2
そうでない場合: #偶数
                結果[evenIndex] = nums[i]
                偶数インデックス += 2
結果を返す
 
 #方法3
クラスソリューション:
    def sortArrayByParityII(self, nums: List[ int ]) -> List[ int ]:
        奇数インデックス = 1
 for i in range(0,len(nums),2): #ステップの長さは2です
            if nums[i] % 2: #偶数が奇数に遭遇
                while nums[oddIndex] % 2: #奇数桁から偶数を見つける
                    奇数インデックス += 2
                nums[i], nums[奇数インデックス] = nums[奇数インデックス], nums[i]
数値を返す

行く

// 方法 1
 sortArrayByParityII関数(nums[] int )[] int {
 // 奇数と偶数をそれぞれnumsに格納します
 偶数、奇数 := [] int {}, [] int {}
 i := 0; i < len(nums); i++ {
  （数値[i] % 2 == 0）の場合{
   偶数 = 追加(偶数、数値[i])
  }それ以外{
   奇数 = append(奇数, 数値[i])
  }
 } 
 
 // パリティ配列をnumsに格納します
 結果:= make([] int , len(nums))
インデックス:= 0
 i := 0; i < len(even); i++ {
  結果[インデックス] = even[i];インデックス++;
  結果[インデックス] = odd[i];インデックス++;
 }
結果を返します。
 }

JavaScript

 //方法1
 var sortArrayByParityII =関数(数値) {
    定数 n = 数値.長さ;
    // 奇数と偶数をそれぞれnumsに格納します
    偶数インデックス = 0、奇数インデックス = 0 とします。
    // オーバーヘッドを節約するために配列サイズを初期化します
    const even = 新しい配列(Math.floor(n/2));
    const odd = 新しい配列(Math.floor(n/2));
    // 配列Aを偶数配列と奇数配列に入れる
( i = 0; i < n; i++ とします){
        if(nums[i] % 2 === 0) even[evenIndex++] = nums[i];
そうでない場合はodd[oddIndex++] = nums[i];
    }
    // パリティ配列をnumsに格納します
    インデックスを 0 にします。
 ( i = 0 とします; i < even.length; i++){
        nums[インデックス++] = even[i];
        nums[インデックス++] = odd[i];
    }
数値を返します。
 }; 
 
 //方法2
 var sortArrayByParityII =関数(数値) {
    定数 n = 数値.長さ;
    const 結果 = 新しい配列(n);
    // 偶数と奇数の添え字
    偶数インデックス = 0、奇数インデックス = 1 とします。
 ( i = 0; i < n; i++ とします){
        if(nums[i] % 2 === 0) {
            結果[evenIndex] = nums[i];
            偶数インデックス += 2;
        }それ以外{
            結果[奇数インデックス] = nums[i];
            奇数インデックス += 2;
        }
    }
結果を返します。
 }; 
 
 //方法3
 var sortArrayByParityII =関数(数値) {
    奇数インデックスを 1 とします。
 ( i = 0 とします; i < nums.length; i += 2){
        if(nums[i] % 2 === 1){ // 偶数位置に奇数がある
            while(nums[oddIndex] % 2 !== 0) oddIndex += 2; // 奇数の位置にある偶数を見つける
            [nums[oddIndex], nums[i]] = [nums[i], nums[oddIndex]]; // 分解代入交換
        }
    }
数値を返します。
 };