根据出现次数对数组进行排序

Question

嗨，我试图根据数组中值的出现次数对数组进行排序。因此，如果我的数组int[] a = new int[]{9,2,4,8,9,4,3,2,8,1,2,7,2,5};我的数组计数应该是：count [i-1]并基于数组的值我的计数数组看起来像这样：1 4 1 2 1 0 1 2 2因此count[0] = 1存储计数为1 count[1] =4并存储计数为2,count[2] = 1将计数存储为3，并且count[8] =2存储9的出现次数。我的计数应该是count[i-1]，以存储出现次数，并根据我应对数组进行排序的次数。第一个问题，我无法将数组a的出现次数存储到count数组中。并根据出现的次数，我如何去存储数组。

Answer 1

第一步是通过你的数组，存储每个数字出现的次数。假设数组可包含的元素只能从1到k，所以我们需要一个count阵列可以存储k元素：

int k = 9; 
int[] count = new int[k]; 

请注意，此数组将在各位置的默认值0，这需要O(k)初始化时间和空间做的，所以它是等价的：

int[] count = {0, 0, 0, 0, 0, 0, 0, 0, 0}; 

因此，最初的计数0所有元素。

现在我们计算数组中的元素。

例如：

int[] a = new int[]{9,2,4,8,9,4,3,2,8,1,2,7,2,5}; 
// Go through each element of this array: 
int n = a.length 
for (int i = 0; i < n; i++) { 
    // Add 1 to the corresponding position in the count array. 
    int position = a[i] - 1; 
    count[position]++; 
} 

这需要O(n)时间，并会导致：

count = {1, 4, 1, 2, 1, 0, 1, 2, 2} 

我们做到了这一点后，数组实际上是排序。我们可以看到这是真的这样做：

int[] sorted = new int[n]; 
int h = 0; 
for (int i = 0; i < count.length; i++) { 
    for (int j = 0; j < count[i]; j++) { 
     // Sum 1 to i to get the original number 
     sorted[h++] = i + 1; 
    } 
} 

System.out.println(Arrays.toString(sorted)); 

这也需要O(n)时间和空间，输出：

[1, 2, 2, 2, 2, 3, 4, 4, 5, 7, 8, 8, 9, 9] 

所以这个算法总时间和空间复杂度为O(n + k)，这意味着它项目数量加上最大和最小键值之间的差异线性运行。