Улучшение производительности - найти максимальное число, равное его появлению в массиве

Question

Вчера я проводил этот тест для работы, и хотя мой код стал на 100% точным, он получил эффективность на 25%. Мне было интересно (не только чтобы лучше в этом тестировании, но и лучше писать код), как я могу сделать этот код лучше. Я предполагаю, что это связано с использованием splice или unset вместо for?

Упражнение было таким: Учитывая массив целых чисел больше 0, я должен вернуть максимальное число, где число равно количеству самого числа. Пример: [2, 3, 2, 5, 7] 2 появляется 2 раза, поэтому fun c должен возвращаться 2. Пример: [2, 3, 2, 3, 5, 3] 2 появляется раз, а 3 появляется 3 раз, но так как 3 больше, 3 является ожидаемым ответом.

function exercise(A){
        // write your code in JavaScript (Node.js 8.9.4)
        let result = 0;
        let amount;
        let prevNumbers = [];
        let continueLoop;

        for(let i = 0; i < A.length; i++){

            amount = 1;

            //Check if number can be an actual result (means that it should be bigger than previous results)
            if(A[i] <= result){ continue; }

            //Check if number was looped before, if it was, continue with next number
            continueLoop = false;
            for( let ix = 0; ix < prevNumbers.length; ix++){
                if(prevNumbers[ix] ==  A[i]){
                    continueLoop = true;
                    break;
                }
            }
            if(continueLoop){ continue; }

            //Check amount of times number appears in array
            for (let ix = i+1; ix < A.length; ix++){
                if(A[i] == A[ix]){
                    amount++;
                }    
            }
            //Check if amount appears equal times to number
            if(A[i] = amount){
                result = amount;
            }
            prevNumbers.push(A[i]);
        }
        return result;
}

Answer 1

В своем решении вы решили проблему, используя два цикла for, что делает алгоритм вашей программы c сложностью как o(n^2). Вместо этого мы можем эффективно решить проблему, используя один l oop, используя линейную сложность o(n).

function exercise(a) {
  let hashMap = {};
  let maxCount = 0;


  for (let i = 0; i < a.length; i++) {
    if (hashMap[a[i]]) {
      hashMap[a[i]]++;
    } else {
      hashMap[a[i]] = 1;
    }
  }

  for (key in hashMap) {
    if (hashMap[key] > maxCount && hashMap[key] == parseInt(key)) {
      maxCount = hashMap[key];
    }
  }

  return maxCount;
}

Answer 2

Если вам важна производительность, ваш код, похоже, реализует алгоритм времени O (n²) (из-за вложенных циклов for..).

Таким образом, вы можете оптимизировать его, выполняя работу в 2 прохода (O (n) -time):

• для вычисления внешнего вида каждого di git, например, с использованием метода Array.prototype.reduce() и сохранения результата в объекте, где клавиши соответствуют самим цифрам, а значения - количеству появлений
• перемещаться выше Object.entries() (снова используя .reduce()), чтобы узнать максимальное значение, передающее описанное условие

Т.е .:

const src =  [2, 3, 2, 3, 5, 3],

      result = Object
        .entries(src.reduce((r,d) => (r[d]=(r[d]||0)+1,r), {}))
        .reduce((max,[key,val]) => key==val && val>max ? val : max, 0)
        
      
console.log(result)

.as-console-wrapper{min-height:100%;}