Для каждого элемента A [i] массива A найдите ближайший j такой, что A [j]> A [i] - PullRequest
Новая
       49

Для каждого элемента A [i] массива A найдите ближайший j такой, что A [j]> A [i]

2 голосов
/ 01 апреля 2010

Дано : массив A[1..n] действительных чисел.

Цель : массив D[1..n] такой, что 

D[i] = min{ distance(i,j) : A[j] > A[i] }

или какое-либо значение по умолчанию (например, 0), когда нет элемента с более высоким значением. Я действительно хотел бы использовать евклидово расстояние здесь.

Пример : 

A = [-1.35, 3.03, 0.73, -0.06, 0.71, -0.21, -0.12, 1.49, 1.41, 1.42]
D = [1, 0, 1, 1, 2, 1, 1, 6, 1, 2]

Есть ли способ победить очевидное решение O (n ^ 2)? Единственный прогресс, который я сделал до сих пор, это то, что D[i] = 1 всякий раз, когда A[i] не является локальным максимумом. Я много думал и придумал НИЧЕГО. Я надеюсь в конечном итоге расширить это до 2D (так что A и D являются матрицами).

Ответы [ 2 ]

1 голос
/ 01 апреля 2010

Так что я немного озадачился этим, но я не придумал ничего лучшего, что работает. Несколько идей:

  • Дополнить массив дополнительной информацией, которую можно получить за O (n) раз или лучше. например, добавить индексы, разницу между соседями и т. д.
  • Поможет ли сортировка (O (n (log n))) каким-либо образом?
  • Похоже, динамическое программирование может быть полезно здесь, если вы можете найти способ решения для каждого элемента на основе решения для его соседей (добавив ответы с информацией, например j для каждого A[i] вместо расстояния, может быть).
0 голосов
/ 27 мая 2010

Сортировка массива от высшего к низшему элементу. Если я правильно понимаю вашу проблему, это дает вам ответ немедленно, так как ближайший больший элемент к любому элементу в исходном списке - тот, что перед ним. Таким образом, вам даже не нужно создавать массив D [], поскольку вычисление его содержимого может выполняться исключительно с использованием массива A []. Первый элемент в отсортированном массиве A [] не имеет большего друга, поэтому ответом на него будет ваш valye по умолчанию (возможно, 0?). Расширение алгоритма для матриц может быть простым (зависит от того, как вы «смотрите» на матрицу) - просто используйте функцию отображения, которая преобразует матрицу в одномерный массив.

...