3

例: A = [4, 1, 3, 2, 3, 3]. 次に、B = [16, 1, 12, 3, 12, 12] を取得します。

アプローチ 1: 各 i について、A を検索し、A[i] 以下の数値を合計します。大雑把に言えば、これには A を n 回横断する必要があるため、O(n^2) 時間かかります。

アプローチ 2: A を並べ替えて A' を取得し、A' の累積和を求めるだけです。これには、A' を 1 回だけ横断する必要があります。したがって、全体の実行時間は、O(n log n) のようなものです。

ただし、これは関係がある場合には機能しません。上記の例では、A' = [1, 2, 3, 3, 3, 6] となるため、cumsum(A') = [1, 3, 6, 9, 12, 16] となりますが、これは同じではありません。 B（ソート済み）として。

O(n log n) で引き続き実行されるようにこれを修正する方法はありますか?

4

5 に答える 5

2

次に、O(n log n)それを達成するための非常に簡単なアプローチを示します。

  1. A を A' にコピーし、A', O(n lg n) を並べ替えます
  2. A' の Prefix Sum を計算し、S、O(n) に格納します。
  3. A をループし、要素 A_i ごとに、A'[j] >= A_i、Ans[i] = S[j]となる A'の最大インデックスをバイナリ検索します。j

Ansは、必要な配列です

以下は、アイデアを説明するサンプル C++ コードです。

#include<bits/stdc++.h>
using namespace std;

int A[6] = {4, 1, 3, 2, 3, 3}, B[6], SUM[6] = {0}, ANS[6];

int main(){
	for(int i=0; i<6; i++) B[i] = A[i];
	sort(B, B+6);
	for(int i=0; i<6; i++) SUM[i] = (i? SUM[i-1]:0) + B[i];
	
	for(int i=0; i<6;i++){
		int j = upper_bound(B,B+6, A[i]) - B;
		ANS[i] = SUM[j-1];
		printf("%d ", ANS[i]);
	}
	puts("");

	return 0;
}

于 2015-06-19T07:20:03.547 に答える
2

より良いアプローチは、A を A' = [1, 3, 6, 9, 12, 16] にソートし、整数の合計を見つけて、cumsum の代わりに、以下のように配列を反復処理することでした。

B[A.length-1] = sum;
for(int i=A.length-2; i=0; i++){
    if(A[i]!=A[i+1]){
        B[i] = sum - B[i+1];
    }
    else{
        B[i] = B[i+1];
    }
}
于 2015-06-19T07:22:23.723 に答える
1

ソートされたアプローチでは、結果を格納する前に、同じ値を持つすべての要素を見つけ (現在はすべて連続しているため、これまで行っていたトラバーサルと同じです)、それらをすべてまとめて処理します: 合計を計算します (すべて)、それぞれの (同じ) 結果を記録します。

于 2015-06-19T05:53:20.967 に答える
1

o（nlogn）でこれを行う簡単な方法があります。

  • 昇順で値に関して配列を並べ替えます。要素のインデックスを並べ替えるには、要素を使用する必要があります。Javaで並べ替えるには、組み込み関数を使用できます

  java.util.Arrays.sort(input, new java.util.Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return Double.compare(a[1], b[1]);
            }
        });

  • 回答を含む一時配列を作成します。
  • ソートされた配列内のすべての要素の合計を計算します。
  • ソートされた配列を後ろから前にトラバースします。
  • 連続した類似番号のカウントを維持します。
  • 次の値と異なる値を取得すると、sum-count*nextvalue で合計を更新します。
  • 現在の値のインデックスに合計を格納します。

これが私のJavaコードです

class Solution
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int[][] input={{0,4}, {1,1}, {2,3}, {3,2}, {4,3}, {5,3
		
          //sort one column with respect to other column in 2d array
		  java.util.Arrays.sort(input, new java.util.Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return Double.compare(a[1], b[1]);
            }
           });
        
           int[] temp=new int[6];   //Answer array
           int sum=0;
           
           for(int i=0;i<6;i++){
               sum=sum+input[i][1];
           }
           
           int count=1;
           temp[input[5][0]]=sum;
           
           for(int i=4;i>=0;i--){
               if(input[i][1]==input[i+1][1]){
                   count++;
                   temp[input[i][0]]=sum;
               }
               else{
                   sum=sum-(count*input[i+1][1]);
                   temp[input[i][0]]=sum;
                   count=1;
               }
           }
           
           for(int i=0;i<6;i++)
              System.out.print(temp[i]+" ");
	}
}

于 2015-06-19T07:16:54.670 に答える