Получить статистический режим в Javascript без использования ассоциативных массивов

Question

Несмотря на то, что я художник, мне нужно вернуть статистический режим из массива чисел. Я хочу, чтобы функция избегала использования ассоциативных массивов (так как мне нужна версия для работы в JavaScript, а также в Maxscript, и было бы лучше использовать одну и ту же базу кода) Maxscript не использует ассоциативные массивы; что жаль, как this является довольно хорошим решением.

Приведенный ниже код работает в первом примере, но не во втором. По предположению, я бы сказал, что массив нуждается в сортировке заранее, но это не сработало (и я опустил его из кода) Может ли кто-нибудь указать, где я ошибаюсь? Спасибо.

var textArr = new Array(); 

arrOne = [0,1,0,2,3,10,10] 
arrTwo = [1,2,3,1,1,1] 

mode_without_associative_arrays(arrOne) // works fine 
mode_without_associative_arrays(arrTwo) // doesn't work 

function mode_without_associative_arrays(arr) 
{ 
    if(arr.length == 0) 
    return null; 

    var collectArr = []; // array 
    var countArr = [] // array to hold the count of each element in collectArr 
    collectArr[0] = arr[0] 
    countArr[0] = 1 
    var mode = arr[0] 
    maxCount = 1; 

    for(var i = 0; i < arr.length; i++) 
    { 
     var ele = arr[i]; 

     for(var j = 0; j < collectArr.length; j++) 
     { 
      var addMe = false; 
      if (collectArr[j] != ele) addMe = true 
     } 

      if (addMe == true) 
      { 
       collectArr.push(ele) 
       countArr.push(1) 
      } 
      else 
      { 
       // count it up 
       countArr[j]+=1 
       if (countArr[j] > maxCount) 
       { 
        maxCount = countArr[j] 
        mode = ele 
       } 
      } 
     } 

     alert("Mode is " + mode + " which appears " + maxCount + " times!") 
     return mode; 
} 

Answer 1

Без ассоциативного массива, я считаю, что оптимальный алгоритм будет:

1. Сортировка массива - О (п § п)
2. Линейно сканирования массива подсчета последовательных вхождений - O (N)

Для шага 2 сравните текущий элемент с предыдущим. Если это то же самое, увеличьте свой счетчик. Если счетчик превышает текущий максимум, помните значение текущего элемента (то есть текущий режим). Если элементы разные, сбросьте свой счетчик на 1.

Answer 2

Что-то вроде этого?

var arrayMode = function (sequence) { 
    if (sequence.length === 0) 
     return 0; 
    var collector = []; 
    var instances = []; 
    var max = 1; 
    collector.push(sequence[0]); 
    var mode = sequence[0]; 
    instances.push(1); 

    for (var i = 1; i < sequence.length; i++) { 
     var index = collector.indexOf(sequence[i]); 
     if (index === -1) { 
      collector.push(sequence[i]); 
      instances.push(1); 
     } else { 
      instances[ index ]++; 
      if (instances[ index ] > max) { 
       max = instances[ index ]; 
       mode = collector[ index ]; 
      } 
     } 
    } 
    return mode; 
} 

В коллектору я буду держать уникальный экземпляр элементов в последовательности и в тех случаях, у меня есть число вхождений каждого отдельного экземпляра в последовательности.