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)or中解决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);
}

一个一个地获取批次：

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 回答
0

我将按如下方式处理它。

  1. 将所有元素及其计数放在平衡的二叉搜索树中。

  2. 现在以一种无序的方式遍历树并继续将元素（with count > 0）放入数组中并将它们的计数减 1。

  3. 创建树的时间复杂度是O(nlgn)，从树中放入元素的时间复杂度是O(n)，空间复杂度是O(n)。

问题是如果没有元素被重复，那么我们就徒劳地创建了树。

于 2013-10-02T20:39:31.347 回答