在未排序的数组中找到第 N 个最高的数字

Question

今天在一次采访中，我被告知要编写一个程序，该程序将输出未排序数组中的第 n 个最高数字，

我用javascript解决了这个问题，程序如下，

var fn50 = function(){
    var reverseSort = function(myArray,highest){
        var x = 0,
            y = 0,
            z = 0,
            temp = 0,
            totalNum = myArray.length, // total numbers in array
            flag = false, // is the numbers sorted in reverse while iteration
            isAchieved = false; // whether we achieved the nth highest

        while(x < totalNum){
            y = x + 1; // start comparing 'yth' number which is next to 'xth' number.

            if(y < totalNum){
                // start comparing 'xth' with the next number, and if 'xth' number less than its next position number, just swipe them
                for(z = y; z < totalNum; z++){

                    if(myArray[x] < myArray[z]){
                        temp = myArray[z];
                        myArray[z] = myArray[x];
                        myArray[x] = temp;
                        flag = true; // if number swiping done ?
                    }else{
                        continue;
                    }   
                }                   
            }

            if(flag){
                flag = false;
            }else{
                x++; // x holds the max number in series, now move to next position to find next highest number 
                if(x > highest){ // if x is what the desired max number which we want flag it and break the loop to escape further iteration.
                    isAchieved = true;
                }   
            }
            if(isAchieved){
                break;
            }
        }

        print(myArray[(highest - 1)]);  
    };

    reverseSort([12,56,78,34,11,100,95],4); // passing the unsorted array of number's, and finding the 4th highest number
};

fn50();

我得到了想要的输出，即上面数组中的答案是 56，这是第四大数字。

但是面试官告诉了一个更好的解决方案。

你能告诉我或给我一个提示，怎么会有更好的解决方案。一些数据结构技术？

Answer 1

排序和选择第kth 个最高的数字需要O(n log(n))时间，其中n是元素的数量。在参考书目中，有中位数算法的中位数，它允许我们k在线性时间内选择第th 个最高或最小的值，无论有什么值k。如果您询问所需元素是否可以是数组的中位数，您可以了解面试官是否考虑了这种算法。中位数是位置 处的元素n / 2，这被认为是最困难的情况。

但是对于面试来说，这是一个复杂的算法。如果k通常较小，则可以根据堆的结构应用以下算法。您可以在线性时间内将数组转换为堆。然后你提取k最大元素的时间。这将需要O(n + k * log(n))时间，这对于小型k = ?(n / log(n)是线性的。

具有k小到恒定数量，如4，具有一个更简单的线性算法。每次我们扫描数组并删除最大的。这将需要O(k * n)时间，因为k是常数，O(k * n) = O(n)。