2

次の形式の重複を含む配列があります。 

arr[]={ 2,9,1,5,1,4,9,7,2,1,4 }

すべての重複要素が最後に向かって移動し、次のように異なるサブ配列にソートされるように、配列をその場でソートしたい: 

arr[]={ 1,2,4,5,7,9, 1,2,4,9, 1 }

指定された配列の整数の範囲がありません。以下は私が試したコードです。このコードは、サブ配列を再帰的に並べ替えてから、重複を最後に移動します。しかし、複雑さに関しては、これは最適な解決策ではありません。または
で解決できるかどうかを提案してください。コード全体は次のとおりです。O(n)O(nlogn)

public static int sortDuplicates(int a[],int start,int end){           
    int i, k,temp;
    if(start==end)
        return 1;
    Arrays.sort(a, start, end);
    k = start;
    for (i = start+1; i < end; i++) {
        if (a[k] != a[i] && a[k]<a[i]) 
        {
           temp=a[k+1];
            a[k+1] = a[i];
            a[i]=temp;
           k++;
        }
    }       
    return sortDuplicates(a,k+1,a.length);  
}
4

2 に答える 2

0

私は次のようにアプローチします。

すべての要素とその数をハッシュマップに入れます。

int[] arr={ 2,9,1,5,1,4,9,7,2,1,4 };
Map<Integer, Integer> map = new HashMap<>();
for (int elt : arr) {
    int val = 1;
    if (map.containsKey(elt))
        val = map.get(elt) + 1;
    map.put(elt, val);
}

バッチを 1 つずつフェッチします。

List<Integer> result = new ArrayList<>();
while (map.size() > 0) {
    List<Integer> subList = new ArrayList<>();     // for the current segment
    Iterator<Integer> it = map.keySet().iterator();
    while (it.hasNext()) {
        int elt = it.next();
        subList.add(elt);
        if (map.get(elt) == 1) { // remove all elements with occurence = 1
            it.remove();       
        } else {                 // reduce occurence by 1
            map.put(elt, map.get(elt)-1);
        }
    }
    Collections.sort(subList);  // sort this segment
    result.addAll(subList);     // append to result
}

for (int i : result) {
    System.out.print(i + " ");
}

これは印刷します

1 2 4 5 7 9 1 2 4 9 1

そして、私が間違っていなければ、それはで実行されO(n log n)ます。

于 2013-08-15T19:02:46.677 に答える