javascript - 以最小的时间复杂度在给定的一组数字中查找第三小的数字

Question

这是一个工作算法，可以找到给定数字集中第三小的数字。

我正在寻找另一种解决方案来满足给定的要求，且时间复杂度较低。

这是工作代码:

Numbers = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
var x = 0;
var y = 0;

function FindThirdSmallestNumber() {


for(var i=0;i<Numbers.length;i++) {

  if (Numbers[i] > Numbers[i+1]) {

    x = Numbers[i];
    y = Numbers[i+1];
      
      Numbers[i] = y; 
      Numbers[i+1] = x;

      i=-1;

  } else {
    //
  }

  

}

console.log(Numbers[2]);

}

FindThirdSmallestNumber();

Answer 1

不确定这是否更快，但更短:

//Use a custom sort function and pass it to the .sort() method
Numbers = Numbers.sort(function(x, y){ return x - y; });
if(Numbers.length > 2){
    //At this point, the 3rd item in the array should be the 3rd lowest
    console.log(Numbers[2]);
}else {
    console.log("There are not 3 numbers in the array.");
}