1
更多，重新排列所述陣列，使得所述元件佈置在交替的次序數量大於給定的整數數組鄰居
a1<a2>a3<a4>a5<a6>a7
可以通過第一分揀做到這一點O（NLogN）並重新安排它。是否有可能在O（n）時間內做到這一點？
A
回答
3
步驟1：在O（n）時間內獲取數組的中位數。我們可以通過使用QuickSelect方法獲得第（n/2）個最大元素來完成此操作。
第2步：現在不要讀這一步，想想解決方案，它的相當清晰。以上一步得到的數字作爲關鍵點並執行quickSort的第一步。
第3步：現在位數左側的元素小於中位數，右側的元素大於中位數。
第4步：從左側和右側交替使用元素，您將獲得我們想要的！
相關問題
- 1. 連鄰居二維數組
- 2. 使用convolve2d查找二維數組中的鄰居數量
- 3. 當大於定義的數量時給予新的數量
- 4. 定義大於無符號整數限制的大數組
- 5. 如何檢查二維數組中的對角線鄰居並將當前值設置爲等於鄰居數
- 6. 查找節點鄰居二維數組
- 7. 有效索引numpy數組鄰居
- 8. 函數來檢查給定的整數數組中的給定位置的元素是否大於其兩個相鄰的元素
- 9. 計數等於數組的相鄰值
- 10. 給定一個整數數組，找出數組中第三大的值
- 11. 無法獲得基於給定整數的字符數組
- 12. 鄰居數KNN算法
- 13. 掃雷鄰居計數
- 14. 在鄰接矩陣中，如何找到給定頂點的鄰居的鄰居？
- 15. 查找差數大於或等於給定數的對的數量
- 16. 查找總和小於給定數組的數組的最大數目
- 17. AS3數學：數組中的最近鄰居
- 18. 從數組中計算等於或大於給定數字的數字
- 19. 找到其總和大於給定整數的最小整數集合
- 20. 給定一個整數數組，找到具有最大產品的相鄰元素對並返回該產品
- 21. 獲取大小在給定一個整數的任意整數
- 22. 整數數量太大
- 23. 在2d數組（生命遊戲）中計數鄰居
- 24. 使用大整數數組
- 25. 對於給定數組大小爲N的三個數的最大乘積
- 26. 尋找給定矢量的k-最近鄰居？
- 27. 查找整數數組中給定數值的最小集合
- 28. 向量/數組到整數
- 29. CSVWriter對於整數數組
- 30. 對於大於給定數字的數字的grep行
是的，它可以在O（n）中完成。你想要答案還是隻是一個提示（因爲這是一個面試問題）？ – Mshnik
提示會很好 –
最後得到O（N）的解決方案。 –