文章目錄

• 問題描述
• 思路介紹
• • 思路一：先快排再直接取元素
  • 思路二：維護一個大小為K的亂序數組進行替換
  • 思路三：維護一個堆最后直接取堆頂元素
  • 思路四：分治法
• 編程實現
• • 第K小元素-思路一-Java編程實現
  • 第K大元素-思路三-Java編程實現
  • 第K小元素-思路四-Java編程實現
  • 第K小元素-思路四-C++編程實現
  • 第K小元素-C++內置函數

問題描述

就是給出一個隨機序列，序列元素可比較，查出第K大元素或者第K小元素。
這是一個經典的算法題，之前也寫過，這里總結一下思路。

思路介紹

思路一：先快排再直接取元素

對于一個隨機序列，快排的性能應該是最好的啦（基礎排序算法），稍加優化性能更佳。
我們先對序列用 數組/順序 表存儲起來?

總結

以上是生活随笔為你收集整理的【算法分析与设计】查找第K大/小元素问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。