Учитывая массив, подсчитайте пары, чьи суммы кратны 60 - PullRequest
Новая
       26

Учитывая массив, подсчитайте пары, чьи суммы кратны 60

0 голосов
/ 13 января 2019

Учитывая массив, как найти число пар (два значения), которые складываются до 60, или значение, кратное 60. Примечание. Должно быть быстрее, чем O (N ^ 2).

Ввод: [10, 50, 30, 90] Выход: 2 Обоснование: 10 + 50 = 60, 30 + 90 = 120 (120 делится на 60)

Ввод: [60,60,60] Выход: 3 Обоснование: 60 + 60 = 120, 60 + 60 = 120, 60 + 60 = 120

Код, который я имею ниже, будет выполняться за O (N) времени, но я не знаю, как позаботиться о парах, которые равны друг другу (т.е. если у вас есть 2 30 значений в массиве, которые добавят 1 к вашему счетчику, но если у вас есть 3 30 значений в массиве, это добавит 3 к вашему счетчику). Я подумал, что мне следует создать комбинированную функцию (то есть 2C2 или 3C2), но это линейная функция, и разве это не вернет функцию к O (N ^ 2)? 

values(myList) {
    var obj = {};
    var count = 0;

    // loop through array and mod each value and insert it into a dictionary
    myList.forEach((elem, index) => {
        if (!obj.hasOwnProperty(elem % 60)) {
            obj[elem % 60] = 1;
        } else {
            obj[elem % 60]++;
        }
    });

    for (var keys in obj) {
        if (obj.hasOwnProperty(60 - keys)) {
            if (60 - keys == keys) {
                // take care of pairs
                // obj[keys] = x --> xC2
            } else {
                count += Math.min(obj[keys], obj[60 - keys]);
                delete obj[keys]
                delete obj[60 - keys];
            }
        }
    }
    return count;
}

Ответы [ 4 ]

0 голосов
/ 14 января 2019

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

function f(A, m){
  const rs = new Array(m+1).fill(0);
  for (let x of A){
    if (rs[(m - x % m) % m])
      rs[m] += rs[(m - x % m) % m];
    rs[x % m]++;
  }
  return rs[m];
}

console.log(f([10, 50, 30, 30], 60));
console.log(f([30, 10, 50, 30, 30], 60));
console.log(f([1, 5, 3, 3, 6, 24], 6));

(Кстати, я не уверен, почему вы делаете различие между двумя числами, которые складываются до 60, и парами, которые суммируются до значения, кратного 60, так как первое содержится в последнем.)

0 голосов
/ 13 января 2019

Комбинация не нужна. Это простая математика.

Это n * (n-1) / 2.

Допустим, у вас есть 4 предмета a, b, c, d.

Пары будут:

  • (а, б)
  • (а, с)
  • (A, D) * +1019 *
  • (б, в) * * один тысяча двадцать-одна * * 1 022 (б, г) * 1 023 *
  • (в, г) * * тысячу двадцать-пять

Для 4 предметов, у нас есть 4 * 3/2 = 6 .

# UPDATE:

Изменить 

count += Math.min(obj[keys], obj[60 - keys]);

до 

count += obj[keys] * obj[60 - keys];

Рассмотрим 2 клавиши - 12 и 48.

  • Ключ 12 имеет элементы - 12,72,132
  • Ключ 48 имеет элементы - 48,108

Технически, вы храните для них количество, которое будет 3 и 2. Если вы наблюдаете, всего нет. пар, которые мы можем сделать, это 3 * 2 = 6 , а не Math.min (3,2);

0 голосов
/ 13 января 2019

Вы можете вычислить n C2 за O (1) раз, потому что n C2 = n ! / ( n −2)! · 2! = n · ( n −1) · ( n −2)! / ( n −2)! · 2! = n · ( n -1) / 2! = n · ( n -1) / 2 .

Тем не менее, вы можете рассмотреть другой подход: вместо отдельного цикла для вычисления count на основе obj, вы можете добавить к count при построении obj. Это может быть более интуитивно понятно, поскольку устраняет необходимость в особых случаях. (До вас.)

Кстати, ваш if (60 - keys == keys) тест неверен; это обнаружит случай, когда keys == 30, но не случай, когда keys == 0. (Также могут быть некоторые другие ошибки, с которыми вам нужно разобраться.)

0 голосов
/ 13 января 2019

обновление: это решение n ^ 2, так что это не отвечает на оригинальный вопрос. 

let values = [60,10,20,50,40,30, 120, 60, 10];

let count = 0;

for (let i = 0; i < values.length; i++){
    for (let j = i+1; j < values.length; j++){
        let v = values[i] + values[j];
        if (v == 60 || !(v % 60)){
            count++;
        }
    }    
}

обновление 2:

Чтобы сделать это n + n * log (n), можно создать отсортированное дерево со значениями мода, а затем перебрать каждое из значений мода и найти значения значения 60 для определения количества пар, составляющих различия. узлы могут быть оптимизированы, сохраняя количество повторений. это решило бы вашу проблему?

...