0

非常基本的问题，但我似乎找不到任何关于如何在 Javascript 中解决它的示例。

我想创建一个函数，在其中传递一个表示“n”的数字，它返回数组中第 n 个最小数字的位置。

例如，如果我这样做：

array = [5,6,1,1,1,8]
n = 3
location = nth_smallest(array, n)

然后位置将等于 4，因为第三个最低的数字是 1，但是我想跳过该数字的前几个重复项。

找到第 n 个最小数字的位置的常见解决方案是：

array = [5,6,1,1,1,8]
n = 3
nth_lowest = array.slice(0).sort()[n]
location = $.inArray(nth_lowest, array)

然而问题是它总是返回位置为 2，因为它知道第三小的数字是 1，但 inArray 函数不关心重复。

有没有办法做到这一点，可能不使用排序功能？它似乎占用了大量的处理，这是一个将经常运行的功能。

4

2 回答 2

1 
// remap array as pairs of value and index
// e.g. change [5, 6, 1] to [[5, 0], [6, 1], [1, 2]]
var augmented_array = array.map(function(val, index) { return [val, index]; });
// sort pairs by the first position, breaking ties by the second
augmented_array.sort(function(a, b) {
    var ret = a[0] - b[0];
    if (ret == 0) ret = a[1] - b[1];
    return ret;
});
// example array will now be [[1, 2], [5, 0], [6, 1]]
// so we get the location by just looking at the second position of a pair
var location = augmented_array[n - 1][1];

如果您希望最后一个位置具有该值，请在排序后执行：

var position = n - 1;
while (position < augmented_array.length - 1 &&
       augmented_array[position][0] == augmented_array[position + 1][0]) {
  ++position;
}
var location = augmented_array[position][1];

或者，如果您想要第一个位置，请执行以下操作：

var position = n - 1;
while (position > 0 &&
       augmented_array[position][0] == augmented_array[position - 1][0]) {
  --position;
}
var location = augmented_array[position][1];

当然，lastIndexOf或者indexOf，正如其他答案之一所建议的那样，会导致更少的代码。

于 2013-04-02T00:55:23.053 回答
0

如果我正确理解您的问题，您正在寻找第 n 个最低数字的最后一个实例的位置？如果是这样，试试这个：

array = [5,6,1,1,1,8];
n = 3;
nth_smallest = array.slice(0).sort()[n];
location = array.lastIndexOf(nth_smallest); // assumes non-ancient browser and/or shim

lastIndexOf可以像这样完成一个haxy shim ：

function lastIndexOf(array,item) {
    return array.join("\x00").match(new RegExp(".*\x00"+item+"\x00"))[0].split("\x00").length-1;
}

这个垫片需要像这样调用：location = lastIndexOf(array,nth_smallest);

于 2013-04-02T00:43:42.903 回答