12

我需要这个 javascript 代码的更优化版本来查找数组中的 3 个最大值。我需要获取最大数字的索引。有没有其他更简单的方法来解决这个问题？

var maxIndex = new Array();
var maxPoints = new Array();
var scoreByPattern = new Array(93, 17, 56, 91, 98, 33, 9, 38, 55, 78, 29, 81, 60);

function findLargest3() {
  maxPoints[0] = 0;
  maxPoints[1] = 0;
  maxPoints[2] = 0; 
  
  for (i = 0; i < scoreByPattern.length; i++) {
    if (scoreByPattern[i] > maxPoints[0]) {
      maxPoints[0] = scoreByPattern[i];
      maxIndex[0] = i;
    }
  }

  for (i = 0; i < scoreByPattern.length; i++) {
    if (scoreByPattern[i] > maxPoints[1] && scoreByPattern[i] < maxPoints[0]) {
      maxPoints[1] = scoreByPattern[i];
      maxIndex[1] = i;
    }
  }

  for (i = 0; i < scoreByPattern.length; i++) {
    if (scoreByPattern[i] > maxPoints[2] && scoreByPattern[i] < maxPoints[1]) {
      maxPoints[2] = scoreByPattern[i];
      maxIndex[2] = i;
    }
  }

  console.log(scoreByPattern + "/******/" + maxPoints[0] + "/" + maxPoints[1] + "/" + maxPoints[2]);
  //alert(maxIndex);
}

findLargest3();

4

14 回答 14

13

修改版

我修改了我的答案以使其更通用。它搜索数组中最大数量的元素的索引：

var scoreByPattern = [93,255,17,56,91,98,33,9,38,55,78,29,81,60];

function findIndicesOfMax(inp, count) {
    var outp = [];
    for (var i = 0; i < inp.length; i++) {
        outp.push(i); // add index to output array
        if (outp.length > count) {
            outp.sort(function(a, b) { return inp[b] - inp[a]; }); // descending sort the output array
            outp.pop(); // remove the last index (index of smallest element in output array)
        }
    }
    return outp;
}

// show original array
console.log(scoreByPattern);

// get indices of 3 greatest elements
var indices = findIndicesOfMax(scoreByPattern, 3);
console.log(indices);

// show 3 greatest scores
for (var i = 0; i < indices.length; i++)
    console.log(scoreByPattern[indices[i]]);

这是一个jsFiddle

于 2012-08-03T08:40:07.683 回答
9

您可以对数组进行降序排序。那么最高 3 个值的索引将是数组中的前三个项目。您可以单独访问它们或使用slice()一次获取它们。下面的示例显示了这两种方法。

var maxPoints = new Array();
var scoreByPattern = new Array(93, 17, 56, 91, 98, 33, 9, 38, 55, 78, 29, 81, 60);

findLargest3();

function findLargest3() {
  scoreByPattern.sort((a, b) => a < b ? 1 : a > b ? -1 : 0);
  
  console.log(scoreByPattern + "/******/" + scoreByPattern[0] + "/" + scoreByPattern[1] + "/" + scoreByPattern[2]);  
  console.log(scoreByPattern.slice(0, 3));
}

于 2012-08-03T08:38:53.477 回答
7

无需对巨大的数组进行排序：在O(n)其中运行优于涉及对原始数组进行排序的任何操作。返回初始数组中最大值及其索引的数组。使用一些更智能的代码，您可以消除小数组的排序，从而获得更好的最坏情况性能。

var ar = [93, 17, 56, 91, 98, 33, 9, 38, 55, 78, 29, 81, 60];
console.log(`input is: ${ar}`);

function getMax(ar){
    if (ar.length <= 3) return ar;
    let max = [{value:ar[0],index:0},
               {value:ar[1],index:1},
               {value:ar[2],index:2}];
    max.sort((a,b)=>a.value-b.value);
        
    for (let i = 3;i<ar.length;i++){
        if (ar[i] > max[0].value){
           max[0] = {value:ar[i],index:i};
           max.sort((a,b)=>a.value-b.value);
        }
    }
    return max;
}

result = getMax(ar);

console.log('the three largest values are:');
console.log(result);

于 2012-08-03T08:52:16.477 回答
4

默认的 javascript 排序回调不能正常工作，因为它按字典顺序排序。10 会在 5 之前变成（因为 1）

我不相信，但是：

my_array.sort(function(a,b) {
    return a-b;
});
于 2012-08-03T08:40:27.920 回答
3

最好的方法是结合使用sort和slice：

这个简单的一个班轮将解决您的问题。

[1, -5, 2, 8, 17, 0, -2].sort(function(a, b){return b - a}).slice(0, 3)

因此，如果您有一个数组并想找到 N 个最大值：

arr.sort(function(a, b){return b - a}).slice(0, n)

对于 N 个最小值：

arr.sort(function(a, b){return a - b}).slice(0, n)
于 2014-02-10T23:31:11.363 回答
2

假设一个相当正态的分布，这应该是相当最优的：

var max_three, numbers = new Array(93,17,56,91,98,33,9,38,55,78,29,81,60);

max_three = (function (numbers) {
    var i, one, two, three;
    one = -9999;
    two = -9999;
    three = -9999;

    for (i = 0; i < numbers.length; i += 1) {
        num = numbers[i];
        if (num > three) {
            if (num >= two) {
                three = two;
                if (num >= one) {
                    two = one;
                    one = num;
                }
                else {
                    two = num;
                }
            }
            else {
                three = num;
            }
        }
    }

    return [one, two, three]

}(numbers))



document.write(max_three)​​​​​​​

98,93,91

于 2012-08-03T08:48:35.277 回答
2

这是针对您的问题的优化解决方案，无需使用排序或其他复杂数组方法：

var maxIndex = new Array();
var maxPoints = new Array();
var scoreByPattern = new Array(93,17,56,91,98,33,9,38,55,78,29,81,60);
function findTop3(n) {
	for (var i = 0; i < n.length; i ++) {
		if (i === 0) {
			maxPoints.push(n[i]);
			maxIndex.push(i);
		} else if (i === 1) {
			if (n[i] > maxPoints[0]) {
				maxPoints.push(maxPoints[0]);				
				maxPoints[0] = n[i];
				maxIndex.push(maxIndex[0]);
				maxIndex[0] = i;
			} else {
				maxPoints.push(n[i]);
				maxIndex.push(i);
			}
		} else if (i === 2) {
			if (n[i] > maxPoints[0]) {
				maxPoints.push(maxPoints[0]);
				maxPoints[1] = maxPoints[0];
				maxPoints[0] = n[i];
				maxIndex.push(maxIndex[0]);
				maxIndex[1] = maxIndex[0];
				maxIndex[0] = i;
				
			} else {
				if (n[i] > maxPoints[1]) {
					maxPoints.push(maxPoints[1]);
					maxPoints[1] = n[i];
					maxIndex.push(maxIndex[1]);
					maxIndex[1] = i;
				} else {
					maxPoints.push(n[i]);
					maxIndex.push(i);
				}
			}
		} else {
			if (n[i] > maxPoints[0]) {
				maxPoints[2] = maxPoints[1];
				maxPoints[1] = maxPoints[0];
				maxPoints[0] = n[i];
				maxIndex[2] = maxIndex[1];
				maxIndex[1] = maxIndex[0];
				maxIndex[0] = i;
			} else {
				if (n[i] > maxPoints[1]) {
					maxPoints[2] = maxPoints[1];
					maxPoints[1] = n[i];
					maxIndex[2] = maxIndex[1];
					maxIndex[1] = i;
				} else if(n[i] > maxPoints[2]) {
					maxPoints[2] = n[i];
					maxIndex[2] = i;
				}
			}
		}
	}
}
findTop3(scoreByPattern);
console.log('Top Elements: ', maxPoints);
console.log('With Index: ', maxIndex);

于 2018-08-03T05:41:02.580 回答
1

编辑：以下所有内容仍然有效。但是，在评论中向我澄清说，原始问题没有要求索引，并且许多答案都是对先前存在的问题的回应。对我原始帖子中的任何草率表示歉意。

但是，即使查看原始问题，我仍然不同意对此类问题推荐一般排序。

我无法相信这些答案中有多少比 OP 提供的解决方案更糟糕。大多数都更简洁，但要么：

  • 不要回答问题。当问题还要求提供前 3 个值的索引时，通常只提供前 3个值。
  • 建议“排序”，但甚至不提及性能、副作用或 Big-O 表示法。

这对 SO 来说可能有点太长了，但我觉得这是相关的信息。

  1. 我需要这个 javascript 代码的更优化版本来查找数组中的 3 个最大值。
  2. 我需要获取最大数字的索引。
  3. 有没有其他更简单的方法来解决这个问题？

我认为 (3) 的意思是“我希望该方法更简洁/可读”，(2) 是“直接在输出中可用的索引”，以及 (1) 的意思是“我希望代码同样高效尽可能”。

从（3）开始，因为它对人们最有用：您的原始算法非常有效，但是您基本上在 3 个循环中的每个循环中都复制了代码；每个循环的唯一区别实际上是索引发生了变化。如果你只是想减少字符数，你可以重写你的算法（有几个小警告1）：

function findLargest3(arry) {
  const max = {
    indices: new Array(0, 0, 0),
    points : new Array(0, 0, 0)
  }
  
  // Inner private function to remove duplicate code
  // Modifies "max" as a side-effect
  function setLargest (idx) {
    const lastMax = max.points[idx - 1] || Number.MAX_VALUE;
    for (let i = 0; i < arry.length; i++) {
      if (arry[i] > max.points[idx] && arry[i] < lastMax) {
        max.points[idx] = arry[i];
        max.indices[idx] = i;
      }
    }
  }
  
  // Get's the 0'th, 1st, and 2nd largest items
  for (let i = 0; i < 3; i++) {
    setLargest(i);
  }
  
  return max;
}

let scoreByPattern = new Array(93, 17, 56, 91, 98, 33, 9, 38, 55, 78, 29, 81, 60);
let max = findLargest3(scoreByPattern);
console.log(scoreByPattern + "/******/" + max.points.join("/"));

除了添加功能之外，我唯一真正需要添加的是：const lastMax = max.points[idx - 1] || Number.MAX_VALUE;. 这仅适用于idx == 0. 因为没有max.points[-1]。我们希望第二次检查始终返回 true，因此如果max.points[idx - 1]不存在，则通过 将其设置为可能的最高值||。

这实际上最终比您的实现慢了大约 4 倍。这种缓慢是由于没有直接修改全局状态（这更快但更难维护）并包括该内部函数而不是代码重复。用你原来的重复代码替换内部函数，让所有其他更改保持不变，最终执行速度提高了 40%，因为它完全避免了函数的创建和调用；但同样更容易阅读。它还使扩展findLargest3变得findLargest5或findLargestN更简单。

此外，它应该是与您的原始解决方案相同的 Big-O（请参阅我对 1 的回答），这与涉及sort;的解决方案不同。这意味着它将与您的原始解决方案一样可扩展，同时更易于阅读和维护。如果您真的需要性能，那么您的原始解决方案几乎没有错误，我什至认为您的原始解决方案比某些已发布的解决方案更好。（例如，从粗略的测试来看，将数组的大小增加到 ~100 个元素会使我的解决方案运行慢约 3 倍，但使用sort运行的解决方案会慢 6 倍以上）。

1注意：您的算法存在一个主要问题，那i就是“全局范围”。如果您编写以下内容，它将运行 fori==0然后永远循环i==scoreByPattern.length& 永远不会完成：

// Outer loop
for (var i = 0; i <= scoreByPattern.length + 1; i++) {
    findLargest3()
}

那是因为您的for (i = 0 ...语句没有引用i& 的“本地”版本，它将回退到在先前范围中定义的版本（或者如果找不到，则为全局版本）。您的循环总是在完成时i设置为scoreByPattern.length，这将更改此外部循环中的值。如果您尝试在循环期间修改迭代器，某些语言和语言结构（foreach例如在 C# 中）实际上不会编译。修复实际上非常简单，它只是说var i或let i在你的循环声明中，然后i只会引用函数本地的变量。

还有一个小问题是您的原始算法忽略了数组中的重复项。如果我将另一个添加93到原始数组的末尾，它仍将顶部值返回为[98, 93, 91]. 我没有在我的解决方案中更改它，因为它可能是故意的（例如，前三个“值”是 98、93 和 91，但 93 恰好出现了两次）。要修复，而不是检查arry[i] < max.points[...您是否只检查它i不在max.indices. 根据重复的数量，这可能会减慢算法速度（无需重写），但假设duplicates << array.length它不会明显变慢。

虽然本身不​​是一个“问题”，但拥有“全局状态”（即scoreByPattern, maxPoints, maxIndex）然后让它们被一个函数突变通常并不理想。它可以在计算上更快，但更难维护。这就是为什么我将声明移到函数体中并将其作为参数maxPoints / maxIndex请求。scoreByPattern有很多场景可以做到这一点（例如，对象成员变量和修改器方法）。但是在这里，findLargest3实际上看起来确实像是一个辅助函数/函数，因此理想情况下不应该有副作用（即修改外部状态/传递给它的参数）。

简要提及（2）：如果索引本身很重要，那么对数组进行排序并没有真正意义，除非在某些非常特殊的情况下（请参阅我对第 1 点的回答）。sort排序是直接在数组上使用 Javascript 方法的“就地”操作。这意味着它将在大多数答案中修改原始数组；所以原始索引实际上丢失了，并且对程序的其余部分也有其他后果。为了使用排序来获取前 N 个值，您必须先复制数组，对副本进行排序，获取前 3 个值，然后遍历原始数组〜 3 次尝试使用indexOf或类似的匹配（并处理有重复）。

这显然是一种资源浪费，因为其中一些答案比原始答案慢了 30 倍。您可以尝试生成“索引”列表而不是值，根据原始数组对它们进行排序，这会稍微快一些。但是在这种我们只想要“前 3 名”的特定情况下（再次，请参阅我对第 1 点的回答），除非我疯了，否则排序几乎总是会变慢。

最后，看看（1），在分析算法时应用一个称为“Big-O notation”的概念很有用。我建议用谷歌搜索它并阅读，但粗略地说：随着输入长度的增加，我们想看看算法的效率如何。scoreByPattern例如，在您的应用程序中，我们有一个长度为的数组N，以及您的问题强加的显式“3 个索引/值”，但能够说“返回顶部M索引”很有用/ 值”。如果scoreByPattern或top M非常短，那么算法的复杂性就无关紧要了，但是如果它们有 100 到 100 的数千个元素，那么它们的计算复杂度就会变得非常重要。

另外，很重要的一点是，对于 JS 中的数组，如果您知道索引，“查找”实际上是一个几乎瞬时的操作~Big O(1)。此外，在 Big-O 中，我们倾向于只查看分析的“主导”项而忽略任何恒定时间因素。例如，如果一个解决方案是10x O(1) + 2x O(N)（10 个恒定时间操作 + 长度列表中每个项目的 2 个操作N），我们说解决方案的 Big-O 是O(N)。这是因为，对于一个相当长的列表，如果我们将 N 的值加倍，所花费的时间大约会加倍。如果它以 O(N 2 ) 操作为界且列表长度加倍，则需要 2 2倍的时间（即慢 4 倍）。

所以你原来的解决方案是：

  • 一些恒定的时间步长
  • 遍历列表一次，进行两次布尔检查和两次赋值
  • 再做一次
  • 第三次这样做

这意味着它类似于kO(1) + 3*cO(N)where k&c是一些常量，将其保留为：O(N)一般来说。如果我们想要“顶级M索引”，您最终会得到：MO(N)最终是O(NM)（即 Big-O of N * M）。为什么这很重要？

sort是 Big-OO(N Log2(N))这意味着什么，比如说，一个约 64 个项目的列表，排序将大致采用64 * Log2(64) == 64 * 6 == ~384ish operations. 因此，将您的解决方案与涉及sort, unless M > Log2(N)， not 排序的解决方案进行比较是可取的。

从这个角度来看：如果您的列表有 100 个项目，那么您需要尝试获得超过 6 个“最大”项目才能更有效地进行排序。如果是 100,000 个项目，您需要尝试获得超过 16 个“最大”项目。在这个用例中，特别是因为您已经明确表示“3”，所以不排序几乎总是更有意义。特别是，因为您正在尝试获取索引；如果您只想要值，那么排序解决方案可能更可取，因为它们很简单。

您可能可以稍微调整您的算法以进一步加快速度，但从粗略的测试来看：我认为您的解决方案已经是这里最快的解决方案。如果您想让维护/阅读/扩展更容易，那绝对是可能的；但这真的不应该以实际增加“时间复杂度”（即使解决方案比 更糟）为代价，O(N)除非它大大简化了实现。

于 2021-01-11T10:24:13.840 回答
0

您为什么不对其进行排序并取第一个（或按升序排序的最后一个）三个元素。

var maxPoints = new Array();
var scoreByPattern = new Array(93,17,56,91,98,33,9,38,55,78,29,81,60);
scoreByPattern.sort();
maxPoints[0] = scoreByPattern[scoreByPattern.length - 1];
maxPoints[1] = scoreByPattern[scoreByPattern.length - 2];
maxPoints[2] = scoreByPattern[scoreByPattern.length - 3];

编辑
如果您需要最大数组的索引，您可以制作一个您排序的副本，然后在原始数组中找到索引：

var scoreByPattern = new Array(93,17,56,91,98,33,9,38,55,78,29,81,60);

// Make a copy of the original array.
var maxPoints = scoreByPattern.slice();

// Sort in descending order.
maxPoints.sort(function(a, b) {
    if (a < b) { return 1; }
    else if (a == b) { return 0; }
    else { return -1; }

});

// Find the indices of the three largest elements in the original array.
var maxPointsIndices = new Array();
maxPointsIndices[0] = scoreByPattern.indexOf(maxPoints[0]);
maxPointsIndices[1] = scoreByPattern.indexOf(maxPoints[1]);
maxPointsIndices[2] = scoreByPattern.indexOf(maxPoints[2]);

另一种无需排序即可找到索引的方法是：

var scoreByPattern = new Array(93,17,56,91,98,33,9,38,55,78,29,81,60);
var maxIndices = new Array(Number.MIN_VALUE, Number.MIN_VALUE, Number.MIN_VALUE);

for (var i = 0; i < scoreByPattern.length; i++) {
  if (maxIndices[0] < scoreByPattern[i]) {
    maxIndices[2] = maxIndices[1];
    maxIndices[1] = maxIndices[0];
    maxIndices[0] = scoreByPattern[i];
  }
  else if (maxIndices[1] < scoreByPattern[i]) {
    maxIndices[2] = maxIndices[1];
    maxIndices[1] = scoreByPattern[i];
  }
  else if (maxIndices[2] < scoreByPattern[i]) maxIndices[2] = scoreByPattern[i];
}
于 2012-08-03T08:37:04.800 回答
0

http://jsfiddle.net/GGkSt/

var maxPoints = [];
var scoreByPattern = [93,17,56,91,98,33,9,38,55,78,29,81,60];

function cloneArray(array) {
    return array.map(function(i){ return i; });
}    
function max3(array) {
    return cloneArray(array).sort(function(a,b) { return b-a; }).slice(0,3);
}
function min3(array) {
     return cloneArray(array).sort(function(a,b) { return a-b; }).slice(0,3);
}

var array=scoreByPattern;
alert("Max:"+ max3(array)[0] +' '+max3(array)[1] +' '+max3(array)[2]);
alert("Min:"+ min3(array)[0] +' '+min3(array)[1] +' '+min3(array)[2]);
于 2012-08-03T08:54:31.857 回答
0 
function get3TopItems(arr) {
  return arr.sort((a, b) => b - a).slice(0, 3);
}
于 2020-05-17T18:39:50.007 回答
0

下面的函数返回一个数组，它的元素是一个固定的二元素数组，第一个元素作为索引，第二个元素作为它的值。

function findTopValues(dataArray, n) {
  var resultArray = [];

  var dataArrayCopy = dataArray.slice();

  var topNArray = dataArrayCopy
    .sort(function (begin, end) {
      return end - begin;
    })
    .slice(0, n);
  for (let ele of topNArray) {
    resultArray.push([dataArray.indexOf(ele), ele]);
  }
  return resultArray;
}

var dataArray = [12,5,20,4,50,23,98,8];

console.log(findTopValues(dataArray,3))

于 2021-01-01T08:37:37.793 回答
0

我创建了一个返回最大元素N索引的函数N（在相等值的情况下，它返回找到的第一个索引）。在代码中，N是qtyMax. 功能有成本O(n)，在最坏的情况下n * qtyMax。

function maxIdxs(arr, qtyMax) {
    var maxIndex = new Array();
    for(var i=0; i<arr.length; i++) {
        var m=0;
        while(m<qtyMax && arr[i]<=arr[maxIndex[m]])
            m++;
        if(m<qtyMax)
            maxIndex.splice(m, 0, i);
    }
    return maxIndex.slice(0, qtyMax);
}

console.log(maxIdxs( [1,23,46,35,20] , 0 )); // []
console.log(maxIdxs( []              , 3 )); // []
console.log(maxIdxs( [1,23]          , 3 )); // [1,0]
console.log(maxIdxs( [1,23,46,35,20] , 3 )); // [2,3,1]
console.log(maxIdxs( [1,40,40,40,40] , 3 )); // [1,2,3]

要获得相应的功能minIdxs（查找最小的索引） ，N您只需<=在>=.while

于 2021-03-23T21:02:20.093 回答
0

这是一个没有排序的解决方案：

let getLargest = (a,n)=>{
    let max,p,b=[],n1;
    for(let i=0;i<n;i++){
        max=a[0]
        p=false
        n1=0
        for(let j in a){
            if(max<a[j]){
                max=a[j]
                p=true
                n1=j
            }
        }
        if(!!p){
            b.push(max)
            a.splice(n1,1);
        }
    }
    console.log(a)
    return b;
}

console.log(getLargest([5.03, 7.09, 6.56,  9.09, 11.11], 3))
console.log(getLargest([5.03, 7.09, 6.56,  9.09, 11.11], 4))
console.log(getLargest([5.03, 7.09, 6.56,  9.09, 11.11], 1))
console.log(getLargest([5.03, 7.09, 6.56,  9.09, 11.11], 2))

对于 n 个循环，我们正在寻找最大值并将其从原始数组中删除并将其推送到新数组。你可以得到n个大元素。

于 2021-12-03T03:47:05.123 回答