0
是否有一種算法對n大小的數組進行排序和O（n）取值範圍[0..k]的整數值從[0..k]獲取整數值的n大小數組的排序和O（n）時間
A
回答
0
是的，有！考慮使用most-significant digit radix sort，有時稱爲二元快速排序。這個算法在原地工作，雖然它需要遞歸堆棧的O（log n）輔助空間（我不知道這是否是一個交易斷言器）。對最大值爲U的n個數字列表進行排序的運行時間爲O（n log U），在您的情況下，因爲k是固定常量，運行時間爲O（n）。
相關問題
- 1. 計數排序O（n + k）時間複雜度是什麼k？
- 2. 在大小爲N的未排序數組中查找K個最小整數
- 3. 合併大小爲n的k個排序數組的下界
- 4. 在O（n）時間的雙維數組排序排序
- 5. 排序大小爲k的problem- N/K的間隔的每個
- 6. 從n個排序數組中找出k個最小數字
- 7. 從小於O（log（n））運行時間的排序數組中搜索
- 8. if（N^2％N == 0）的大O符號的時間
- 9. 爲O整數的外部排序（N日誌N）的讀取和O（N）寫道：
- 10. 在O（N * log（N））時間比較兩個不同大小的int數組？
- 11. 如何將n個排序列表中的平均長度K排序爲O（n * log K）時間？
- 12. 從n個排序的數組中總共獲得k個最小值的時間複雜度？
- 13. 將哈希錶轉換爲O（log（k）* k + n）中的排序數組
- 14. 長度爲N的數組可以包含值1,2,3 ... N^2。可以在O（n）時間排序嗎？
- 15. O（logn）中從0〜N的位計數
- 16. 返回列表[1，n，n^2，n^3，...，n^k]的函數powers（n，k），其中k是整數
- 17. 在O（1）時間返回ak大小數組的前n個元素時間
- 18. Java讀取n個整數的k行
- 19. 排序在O（n + mlogm）時間陣列
- 20. 算法的漸近分析：如何在時間O（k log k + n）中插入k個新元素到大小爲n的排序列表中
- 21. 下面的函數是O（n）時間和O（1）空間，其中n = | A |？
- 22. 排列給定的小於O（n^2）的整數列表
- 23. 獲取k值的所有排列（k = 1 ... n）
- 24. 排序在O（n）的單次通過的時間複雜度的整數elemets
- 25. 數組大小爲n的形式爲k = 2^n的鍵的查找表
- 26. 隨機從大小爲n的數組
- 27. O（nlog * n）和O（n）之間？
- 28. 從大小爲n的數組中缺少m個整數
- 29. 時間複雜度O（N日誌（log n）的）+ N O（L）
- 30. 如何查找在O（log（N））時間內的特定範圍內的排序數組中的整數數量？
計數排序：http://en.wikipedia.org/wiki/Counting_sort沒有到位，需要額外的複製操作來複制源代碼。 O（n + k） –
順便說一句，如果數據只包含數字（沒有附加信息），可以在適當的位置完成，在這種情況下，原始數組可以從直方圖完全重建。 –