Интервью Вопрос - Какие цифры появляются чаще всего в списке интервалов

Question

Я только слышал об этом вопросе, поэтому не знаю точных пределов.Вам дан список целых положительных чисел.Каждые два последовательных значения образуют замкнутый интервал.Найдите число, которое появляется в большинстве интервалов.Если два значения появляются одинаковое количество раз, выберите наименьшее.

Пример: [4, 1, 6, 5] приводит к [1, 4], [1, 6], [5, 6] с 1, 2, 3, 4, 5, каждое из которых отображается дважды.Правильный ответ будет 1, так как он наименьший.

Я, к сожалению, понятия не имею, как это можно сделать, не прибегая к подходу O (n ^ 2).Единственной оптимизацией, о которой я мог подумать, было объединение последовательных нисходящих или восходящих интервалов, но на самом деле это не работает, поскольку [4, 3, 2] будет считать 3 дважды.

Редактировать: Кто-то прокомментировал (но затем удалил) решение с этимссылка http://www.zrzahid.com/maximum-number-of-overlapping-intervals/. Я считаю этот вариант самым элегантным, хотя он и не учитывает тот факт, что некоторые элементы в моих входных данных будут одновременно началом и концом некоторых интервалов.

Answer 1

Основное наблюдение состоит в том, что результатом будет одно из чисел на входе (доказательство оставлено читателю как простое упражнение, яда яда).

Мое решение будет вдохновлено решением @ Prune. Важным шагом является сопоставление входных чисел с их порядком в пределах всех различных чисел на входе.

Я буду работать с C ++ std. Сначала мы можем загрузить все числа в набор. Затем мы можем создать карту из этого, которая отображает число в его порядке в пределах всех чисел.

int solve(input) {
  set<int> vals;
  for (int n : input) {
    vals.insert(n);
  }
  map<int, int> numberOrder;
  int order = 0;
  for (int n : vals) {  // values in a set are ordered
    numberOrder[n] = order++;
  }

Затем мы создаем массив процессов (аналогично решению @ Prune).

  int process[map.size() + 1];  // adding past-the-end element
  int curr = input[0];
  for (int i = 0; i < input.size(); ++i) {
    last = curr;
    curr = input[i];
    process[numberOrder[min(last, curr)]]++;
    process[numberOrder[max(last, curr)] + 1]--;
  }
  int appear = 0;
  int maxAppear = 0;
  for (int i = 0; i < process.size(); ++i) {
    appear += process[i];
    if (appear > maxAppear) {
      maxAppear = appear;
      maxOrder = i;
    }
  }

Наконец, нам нужно найти найденное значение на карте.

  for (pair<int, int> a : numberOrder) {
    if (a.second == maxOrder) {
      return a.first;
    }
  }
}

Это решение имеет O (n * log (n)) сложность времени и O (n) пространственную сложность, которая не зависит от максимального размера входного числа (в отличие от других решений).

Answer 2

Сортировка интервалов в зависимости от их начального значения. Затем проведите линию смахивания слева (глобальное наименьшее значение) вправо (глобальное максимальное значение). В каждой точке встречи (начало или конец интервала) подсчитайте количество пересечений с линией прокрутки (в O(log(n))). Временная сложность этого алгоритма будет O(n log(n)) (n - количество интервалов).

Answer 3

Думайте об этом как о скобках: ( для начала и интервала, ) до конца.Теперь проверьте границы для каждой пары [a, b] и маркеры начала / конца интервала подсчета для каждой позиции: нижнее число получает начало интервала слева;большее число получает близкий интервал вправо.Для данного ввода:

Process [4, 1]
result: [0, 1, 0, 0, 0, -1]
Process [1, 6]
result: [0, 2, 0, 0, 0, -1, 0, -1]
Process [6, 5]
result: [0, 2, 0, 0, 0, -1, 1, -2]

Теперь просто сделайте накопительную сумму из этого списка;позиция наибольшего значения - ваш желаемый ответ.

result: [0, 2, 0, 0, 0, -1, 1, -2]
cumsum: [0, 2, 2, 2, 2,  1, 2,  0]

Обратите внимание, что окончательная сумма должна быть 0 и никогда не может быть отрицательной.Наибольшее значение равно 2, которое появляется первым в позиции 1. Таким образом, 1 - это наименьшее целое число, отображающее максимальное (2) количество.

Нет, это один проход на входе и один проход в диапазоненомера.Обратите внимание, что с помощью простой таблицы значений вы можете сэкономить хранилище.Таблица обработки будет выглядеть примерно так:

[(1,  2)
 (4, -1)
 (5,  1)
 (6, -2)]

Если у вас есть ввод с интервалами, начиная и заканчивая номером, то вам нужно сначала обработать запуски.Например, [4, 3, 2] будет выглядеть так:

[(2,  1)
 (3,  1)
 (3, -1)
 (4, -1)]

ПРИМЕЧАНИЕ : поддержание отсортированного списка вставок составляет O (n ^ 2) время включенияразмер ввода;последующая сортировка списка O (n log n) .Либо это O (n) пробел.

Мое первое предложение, индексирование по самому числу, это O (n) время, но O (r) пробел в диапазоне входных значений.[

Answer 4

Если максимальное число в массиве диапазонов меньше максимального размера массива, мое решение будет работать со сложностью o (n).

1- Я создал новый массив для обработки диапазонов ииспользуйте это, чтобы найти числа, которые появляются больше всего во всех интервалах.Для простоты давайте воспользуемся вашим примером.вход = [1, 4], [1, 6], [5, 6].давайте вызовем новый процесс массива и дадим ему длину 6, и он инициализируется с 0s process = [0,0,0,0,0,0].

2-Затем переберите все интервалы и отметьте начало с (+1), а ячейку сразу же после окончания моего диапазона с (-1)

• для диапазона[1,4] процесс = [1,0,0,0, -1,0]

• для диапазона [1,6] процесс = [2,0,0,0, -1,0]

• для диапазона [5,6] process = [2,0,0,0,0,0]

3- Массив процессов будет работать как накопительный массив.Инициализируем переменную, назовем ее emerge = process [0], которая в нашем случае будет равна 2.Пройдите процесс и продолжайте накапливать, что вы можете заметить?Появятся элементы 1,2,3,4,5,6 = 2, потому что каждый из них появился дважды в заданных диапазонах.

4 - Максимизируйте, пока вы просматриваете массив процессов, вы найдете решение

Публичный класс Test {

public static void main(String[] args) {

    int[] arr = new int[] { 4, 1, 6, 5 };
    System.out.println(solve(arr));


}

public static int solve(int[] range) {
    // I assume that the max number is Integer.MAX_VALUE

    int size = (int) 1e8;
    int[] process = new int[size];

    // fill process array
    for (int i = 0; i < range.length - 1; ++i) {
        int start = Math.min(range[i], range[i + 1]);
        int end = Math.max(range[i], range[i + 1]);

        process[start]++;
        if (end + 1 < size)
            process[end + 1]--;
    }
    // Find the number that appears in most intervals (smallest one)
    int appear = process[0];
    int max = appear;
    int solu = 0;
    for (int i = 1; i < size; ++i) {
        appear += process[i];

        if (appear > max){
            solu = i;
            max = appear;
        }

    }
    return solu;
}

}