2017-01-18 17 views
1

これをどのようにo(n)またはoo(n^2)の代わりにo(log n)またはo(n)の時間複雑度を持つようにこのコードを修正する方法

授業が終わった後、児童のグループが外に出て、彼の誕生日を祝うためにポリカルプスを訪れることにしました。 i番目のグループはsiの友達(1≤si≤4)で構成されており、一緒にPolycarpusに行きたいと思っています。彼らはタクシーでそこに着くことに決めました。各車は最大4人の乗客を運ぶことができます。各グループのすべてのメンバーが同じタクシーに乗る必要がある場合、子どもが必要とする最小限の車の台数(1台のタクシーは複数のグループを利用できます) あなたはすべてのグループを検討する必要があるので、私のアプローチであるが、Oで(N^2)

import java.util.*; 

public class taxi { 
    public static void main(String[] args) { 
    Scanner sc = new Scanner(System.in); 
    while (sc.hasNext()) { 
     int cars = 0; 
     int groups = sc.nextInt(); 
     int[] a = new int[groups]; 
     for (int i = 0; i < a.length; i++) { 
     a[i] = sc.nextInt(); 
     } 
     Arrays.sort(a); 
     for (int i = a.length - 1; i > 0; i--) { 

     if (a[i] == 4) { 
      cars = cars + 1; 
     } else { 
      if (a[i] == 0) { 
      break; 
      } else { 
      int y = 4 - a[i]; 
      for (int j = i - 1; j >= 0; j--) { 
       if (y - a[j] == 0) { 
       a[j] = 0; 
       break; 
       } 
       if (y - a[j] > 0) { 
       y = y - a[j]; 
       a[j] = 0; 
       } 
      } 
      cars = cars + 1; 
      Arrays.sort(a); 
      } 
     } 
     } 
     if (a[0] != 0) { 
     cars++; 
     } 
     System.out.println(cars); 
     cars = 0; 
    } 
    } 
} 
+1

[codereview.se]に適しています。 –

答えて

2

後あなたは(Nを記録)Oを実現することは決してないだろう。

これは、グループセットとキャッシュの1つのトラバーサルで実行できます。つまり、O(N)です。

各グループについて、サイズを数えます。

  1. 4の場合は、タクシーを追加します。
  2. 3の場合、キャッシュされていない場合はキャッシュされた1とペアを作成します。
  3. 1の場合、キャッシュされていない場合はキャッシュされた3つのグループとペアを作成します。
  4. 2の場合は、キャッシュされていない場合はキャッシュされた2とペアを作成します。

キャッシュを調べます。次に、1

+0

私はプログラミングに慣れていないので、あなたはキャッシュが何を意味するのか教えていただけますか? – marwagaser

+0

物を保管する場所。あなたの場合、(n)番目の要素の値がn人のグループの数で十分であるような3つの要素の 'int'配列、ArrayアクセスはO(1)です。 – Bathsheba

+0

だから私は、[5,2グループのそれぞれの学生の数である[1,2,2,3,4]があれば、3サイズの配列は何でしょうか?[1,2,3]? – marwagaser

1

バトシェバが提案ものと同様の溶液の残りのグループをペア1の1つ以上のグループと2の任意のグループをペアが、代わりにキャッシュの各サイズのグループの数に基づいて:

グループのリストを一度反復し、各サイズの数を数えます。これはO(n)時間を必要とし、あなたに次のカウンタを提供します:

int size1 = ... 
int size2 = ... 
int size3 = ... 
int size4 = ... 

は今、(この計算はO(1)かかります)これらのカウンタに基づいて、車の数を計算します。

int carsCount = size4; // add full cars (groups of 4) 
carsCount += size3; // each group of 3 requires a separate car 
carsCount += size2/2; // pairs of groups of 2 
size1 -= size3; // group as many groups of 1 with groups of 3 as possible 
boolean odd2s = (size2 % 2) == 1; 
if (odd2s) { 
    carsCount++; // add a car for the odd group of 2 
} 
if (size1 > 0) { 
    if (odd2s) { 
     size1 -= 2; // two groups of 1 can be paired with the odd group of 2 
    } 
} 
if (size1 > 0) { 
    carsCount += (size1 + 3)/4; // any remaining groups of 1 are grouped in groups of 4 
} 
+0

ヒープありがとう! – marwagaser

0

のみ4グループのサイズがあります:1 1,2,3または4を指定します。

各サイズの配列を初期化し、グループサイズの配列を渡し、グループサイズの適切な配列要素を増やします。 O(n)ある

// Count the number of groups of each size. 
int[] counts = new int[5]; // 1 more, just to use 1-based indexing. 
for (int e : a) { 
    ++counts[e]; 
} 

次に、このように通過:

int numTaxis = counts[4];  // 1 taxi for each 4-sized group. 
       + counts[3];  // 1 taxi for each 3-sized group. 
       + counts[2]/2; // 1 taxi for each pair of 2-sized groups. 

// But you can put a 1-sized group in each 3-sized group's taxi. 
int unmatched1s = Math.max(0, counts[1] - counts[3]); 

// You require ceil(unmatched1s/4) taxis for the 1-sized groups - 
// - but increase by 1 to handle the possibility of unpaired 2-sized group. 
numTaxis += (unmatched1s + counts[2] % 2 + 3)/4; 

O(n)、全体を意味し、O(1)です。

関連する問題