javascript - 如何从 Javascript 数组中获取两个最大的整数并将值返回给 DOM？

Question

我编写了一个解决方案来获取通过表单输入的整数列表。有用。它为您提供两个最大整数的总和并将其发布在 DOM 中。但是，对于包含 100 万个整数的大型数组，它的效率不是很高。

如何改进此解决方案以提高效率。

应用程序.js

 // This function reverses the order of the array and places the biggest numbers first
 function sortNumber(a, b) {
   return b - a;
 }


 // this function is used to ensure the user didn't enter any letters
 function getArray() {
   var alphaExp = /^[a-zA-Z]+$/;

   // This function takes the array, orders it, adds the sum of the two largest numbers and returns the value
   
   function sumOf(x) {
     
       // Sort the ary with the sortNumber function
       array.sort(sortNumber);
   
     // Then we add the two biggest numbers of the array and save it to the result variable.
     
       var result = array[0] + array[1];
     
       // Then we share the result with the user by updating the browser
       var myHeading = document.querySelector('h2');
       myHeading.textContent = "The sum of your two biggest numbers is: " + result;
       
     // Like a good student, it's important to show your work
       var showYourWork = document.querySelector('h3');
       showYourWork.textContent = array[0] + " + " + array[1] + " = " + result;
     }
     // This grabs the value of the input
   var arrayField = document.getElementById('arrayField').value;

   if (arrayField.match(alphaExp)) {
     
     // Fail if user enters letters
     var raiseError = document.querySelector('h5');
     raiseError.textContent = 'No not letters! We want numbers!!';
   } else {
     var array = JSON.parse("[" + arrayField + "]");
     if (arrayField.length < 2) {
       
       // If the user enters only 1 number, tell them to enter more!
       var raiseError = document.querySelector('h5');
       raiseError.textContent = 'Please enter atleast two numbers seperated by commas for us to add!'
     } else {
       
       // When the user enters a list of numbers, run the sumOf function.
       sumOf(arrayField);
       
       //Make the error go away
       var raiseError = document.querySelector('h5');
       raiseError.textContent = '';
     }
   }
 };

 // use an eventlistener for the event (This is where the magic happens)
 var subButton = document.getElementById('subButton');
 subButton.addEventListener('click', getArray, false);

Answer 1

你不必对它进行排序，只需线性搜索两个最大的即可:

编辑:下面的代码现在应该可以工作，并且渐近地比 OP 的代码快。假设一个随机列表，OP 首先进行排序，这可以在 O(n log n) 中完成。我的代码使用 c = 2 对 O(cn) 中的列表进行线性搜索(这两个循环不是必需的，但很简单)。 ceil(n log n) = 2n 且 n 为正整数的解决方案是 14，即对于每个长于 14 个条目的列表，下面的代码更快。例如:对于一百万个条目，关系是 13,815,511 到 2,000,000，快了六倍多。您可以在将运行时间减半的单个循环中执行相同的操作(理论上，但由于更好的局部性，它也快了一点点)。

function maxtwo_wrong(a){
    var b1 = -Infinity;
    var b2 = -Infinity;

    for (var i=0; i < a.length; i++) {
        if (a[i] > b1) {
            b1 = a[i];
        }
    }
    for (var i=0; i < a.length; i++) {
        if (a[i] > b2 && a[i] < b1) {
            b2 = a[i];
        }
    } 
    return [b1,b2];
}

EDIT-2: maxtwo_wrong上面的代码好像不太符合要求，所以我又写了一个maxtwo_right放在下面。 OP，请告诉我哪个符合您的要求，以便我删除错误的。

EDIT-3:使它更简单和正确。

function maxtwo_right(a){
    var b1 = -Infinity;
    var b2 = -Infinity;

    for (var i=0; i < a.length; i++) {
        // If the current entry is bigger than variable b1
        // keep the old value in the variable b2 and set b1 to the
        // value of the current entry
        if (a[i] > b1) {
            b2 = b1;
            b1 = a[i];
        }
        // if the current entry equals b1 set the variable b2 to
        // the value of the current entry
        else if(a[i] === b1){
            b2 = a[i];
        }
    }
    // return the sum of the two variables as requested
    return b1 + b2;
}