Topic: suppose sequence is composed of n different keyword records (a record have a keyword), request without sorting choose keywords from big to small order before k (kHave a great god will? Looked through entire network also didn't find relevant explanation,,,,

CodePudding user response:

Title description I have a problem, not the sort, select keywords from big to small order before k... Not sorted to select the order from large to small???????
Description according to the topic, not sort is impossible to choose from big to small, but not completely sort number n,
I think there are about three kinds of diminishing (efficiency) :
1. The recursive version of the quick change, after every group compared with k, only continue to recursive left or right, not about recursion (close to every time cut in half and time complexity O (n), find out after the first k, k before to local sorting,
2. The chairman of the tree, the tree, chairman of the chosen k, and the method 1, partial order
3. The heap sort of incomplete, build the minimum heap, heap sort according to the first k from big to small order to stop (compared to sort all provinces is not too much time)

CodePudding user response:

Heap sort, this is the classic TOPN problem to establish a minimum heap size of k will record traverse again into the heap of the last remaining is the greatest k records, can be used in Java PriorityQueue to implement reference https://my.oschina.net/leejun2005/blog/135085 topk part inside

CodePudding user response:

Don't sort, and directly traverse all the nodes, the large number of preserved k before, just like to find a reasonable maximum (with Max variable stores the value of the largest, traverse all the nodes, meet than Max assignment into Max),,, just change the Max variable to Max array,

CodePudding user response:

Don't sort does not mean not to compare

CodePudding user response:

Without sorting right should be said that contains n key collection sorting, this method is much more

CodePudding user response:

The problem without a solution, if the time complexity should be lowest heap sort O (n * lgK)
But the topic request seems to be a minimum mathematical sense,,,,,,, feel is too complex, probably no solution