在给定的一组时间复杂度最小的数字中寻找第三小的数字

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.");
}

Answer 2

一种选择是使用一个由迄今为止最小的三个数字组成的单独的排序数组。每当遇到小于第三个最小值(排序数组中的最后一个(的数字时，将第三个索引重新分配给新数字，然后再次排序：

const numbers = [3, 2, 55, -10, -55, 5, 3, 2, 1, -5, 33, 9, -1, 4, 5];
const sortNumeric = (a, b) => a - b;
function FindThirdSmallestNumber(input) {
const [smallestSoFar, numbers] = [input.slice(0, 3), input.slice(3)];
smallestSoFar.sort(sortNumeric);
numbers.forEach((num) => {
if (num < smallestSoFar[2]) {
smallestSoFar[2] = num;
smallestSoFar.sort(sortNumeric);
}
});
return smallestSoFar[2];
}
console.log(FindThirdSmallestNumber(numbers));

注意，实现sort，整个数组(就像其他答案一样(是O(N log N)，而sorting这里只在3大小的数组上完成，这明显不那么复杂(我认为O(N log 3)，相当于O(N)(

Answer 3

这个应该简单得多。也不确定这是否更快，但在最简单/明显的情况下，代码更少=性能更好。

我只是将数组升序排序，然后根据索引获取值。因此，使用此代码，您可以获得任何位置；最低、第二低、第三低等，只要你的指数不超出范围。

const input = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];

function getLowestByRank(data, rank) {
data.sort(function(a, b){ return a - b });

return data[rank - 1];
}

console.log(getLowestByRank(input, 3))
console.log(getLowestByRank(input, 2))
console.log(getLowestByRank(input, 4))

Answer 4

您可以使用Math.min函数来确定最小值，直到找到您的X最小值：

Numbers = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
function FindSmallestNumber(arr, limit) {
var min = '';
for(var counter = 1; counter <= limit; counter ++) {
min = Math.min.apply(Math, arr);
arr.splice(arr.indexOf(min), 1);
}   
console.log(min);
}
FindSmallestNumber(Numbers, 3); //3rd smallest number

Answer 5

我认为对数组进行排序可能是最快的方法，但也许你想避免内置排序。另一种选择是Chris Li建议的：迭代值，保持3个值的最低值，然后返回三个值中的最高值。

我假设您希望避免使用内置方法，所以这只使用一些基本的数组方法，并手动执行其他所有操作。

// Avoid Math.max
function getMax(arr) {
var max = -Infinity;
for (var i=0, iLen=arr.length; i<iLen; i++) {
if (arr[i] > max) max = arr[i];
}
return max;
}
// If data.length < 4, just returns largest value
// Iterates over data once
function get3rdSmallest(data) {
// Helper to insert value in order
// Expects arr to be length 3 or smaller
function insertNum(arr, num) {
if (!arr.length || num < arr[0]) {
nums.unshift(num);
} else if (num > arr[arr.length-1]) {
arr.push(num);
} else {
arr[2] = arr[1];
arr[1] = num;
}
}

var num, nums = [];
if (data.length < 4) {
return getMax(data);
}

for (var i=0, iLen=data.length; i<iLen; i++) {
num = data[i];

// Insert first 3 values sorted
if (nums.length < 3) {
insertNum(nums, num);

// If num is smaller than largest value in nums,
// remove move largest and insert num
} else if (num < nums[2]){
nums.splice(-1);
insertNum(nums, num);
}
}
// Return highest (last) value in nums
return nums[2];
}
var data = [3,2,55,-10,-55,5,3,2,1,-5,33,9,-1,4,5];
console.log(get3rdSmallest([-4,-22]));    // -4
console.log(get3rdSmallest([4,0,1,7,6])); //  4
console.log(get3rdSmallest(data));        // -5