时间复杂度问题，我认为用目前的数据是不可能的

Question

问题是：

. Let A be an array of integers in the range {1, ..., n}. Give an O(n) algorithm that gets rid of duplicate numbers, and sorts the elements of A in decreasing order of frequency, starting with the element that appears the most. For example, if A = [5, 1, 3, 1, 7, 7, 1, 3, 1, 3], then the output should be [1, 3, 7, 5].

问题是，如果我们想知道从 1 到 n 的每个数字出现多少次，我们需要运行的 A 其长度为 m（m = A.length，因为我们不知道）。

使用桶排序，当 m = O(n) 时，这是可能的。

我觉得这个问题有问题，因为如果m = θ(n)，甚至m = Ω(n)。

所以基本上我认为如果不对 m 进行分类，就不可能实现 O(n)。

如果有人知道解决这个问题的方法，我会很高兴。谢谢

Answer 1

我同意你所说的问题是不可能的 - O(n) 时间甚至不足以读取数组的所有元素，这意味着你不一定能找到所有不同的元素给定的时间范围。

但是，如果您假设数组的大小为 O(n)，那么正如您所指出的，这可以通过计数排序来完成。

您可能想联系给您提出此问题的人，以指出该细节。 :-)

希望对您有所帮助！

Answer 2

排序是另外一回事。也就是说，使用 radix sort 你可以获得 O(kn) 时间，如果 k 是常数。

主要关心的应该是如果你能以某种方式设法运行你的在 O(N) 时间内进行总和，那么您仍然会获得收益，即 O(radixSort) + |O(n)| ~ |O(kn+n)| ~ |O(kn)| 最后。

如果您认为这样的方法。将元素作为散列table的键，将它们的总和作为散列table.

的值

foreach (elements-i in the array){
// element is already in the hashTable
if (hashMap.contains(element-i)){
//take its value (its sum) and update it.
hashMap.put (element-i, hashMap.get(elements-i)+ 1);
}

// element-i hasn't been there
// so put it
else {
// key-value
hashMap.put(element-i, 1); // sum is initialized as 1
}
}

这运行秒 O(N) 时间（最坏情况）。在你的情况下，元素不足以在散列过程中产生一些冲突所以实际上 hashMap.put ， hashMap.contains或 hashMap.get 运行 O(1) 时间。

终于。您可以选择任何排序方法来对散列进行排序 table。无论产生的排序时间复杂度如何，都将是整个过程的时间复杂度。

时间复杂度问题，我认为用目前的数据是不可能的

Time complexity question, i think it is impossible with current data

sorting

time

complexity-theory

time-complexity