根據出現次數對數組進行排序

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)，這意味着它項目數量加上最大和最小鍵值之間的差異線性運行。