?1.這個通過partition實現topk，時間復雜度是o(logn*logn)，也就是0(n),但需要修改原數組的順序

下面這個代碼本身有一些錯誤，并且throw excption會在牛客上報錯

class Solution { public:vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {vector<int> result;int length = input.size();if(input.empty() || length <= 0 || k <= 0 || length < k)return result;int start = 0;int end = length - 1;int index = partition(input,length,start,end);while(index != k-1){if(index > k-1){end = index-1;index = partition(input,length,start,end);}else{start = index + 1;index = partition(input,length,start,end);}}for(int i = 0;i <= index;i++)result.push_back(input[i]);return result;}int partition(vector<int> &input,int length,int start,int end){if(input.empty() || length <= 0 || start < 0 || end >= length)throw new exception("Invalid Parameters");int small = -1;for(int i = start;i <= end;i++){if(input[i] <= input[end]){start++;if(start != i)swap(&input[start],&input[i]);}}small++;swap(&input[small],&input[end]);return small;} };

?正確代碼

class Solution { public:vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {vector<int> result;int length = input.size();if(input.empty() || length <= 0 || k <= 0 || length < k)return result;int start = 0;int end = length - 1;int index = partition(input,start,end);while(index != k-1){if(index > k-1){end = index - 1;index = partition(input,start,end);}else{start = index + 1;index = partition(input,start,end);}}for(int i = 0;i < k;i++)result.push_back(input[i]);return result;}int partition(vector<int> &input,int start,int end){int small = start - 1;for(int i = start;i < end;i++){if(input[i] < input[end]){small++;if(small != i)swap(input,small,i);}}small++;swap(input,small,end);return small;} void swap(vector<int>& input,int a,int b){int tmp = input[a];input[a] = input[b];input[b] = tmp;} };

2.用大根堆的做法的時間復雜度是o(nlogk)

轉載于:https://www.cnblogs.com/ymjyqsx/p/9535484.html

總結

以上是生活随笔為你收集整理的topk两种解法的全部內容，希望文章能夠幫你解決所遇到的問題。

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