Как найти наибольшую разницу в Kth в int []?

Question

У меня есть вопрос по алгоритму.

Например, существует массив int[], например [1,5,4,3,7,2].

Я хочу найти k-ую наибольшую разницу в этом массиве, например:

array[i] - array[j] = kth largest difference

(индекс i должен быть меньше j, а array[i] должен быть больше array[j]).

Выходные данные возвращают j в этом вопросе.

Моя текущая идея:

• Я могу построить int[][] для хранения всей разницы в массиве.
• Затем рассортируйте их и найдите разность k-го числа.

Но сложность времени составляет O(n^2).

Есть ли лучшие решения?

Answer 1

Это может быть сделано в сложности O( N * logN + N * logValMax ). Сначала давайте отсортируем массив. После этого мы можем построить функцию countSmallerDiffs( x ), которая подсчитывает, сколько разностей меньше или равно x в массиве, эта функция имеет сложность O (N) с использованием двух указателей. После этого мы можем выполнить двоичный поиск результата в диапазоне minVal-maxVal. Нам нужно найти p такой, который удовлетворяет countSmallerDiffs( p ) <= k < countSmallerDiffs( p + 1 ). Ответ будет p.

Надеюсь, это поможет вам! Удачи!

Answer 2

Пример:

results = []

a_new = [(1,0), (2,5), (3,3), (4,2), (5,1), (7,4)]

start_index = 0
end_index = len(a_new) - 1

i = -1
j = -1
diff = 0

while True:
    if(a_new[start_index][1] < a_new[end_index][1]):
        i = a_new[start_index][1]
        j = a_new[end_index][1]
        diff = a_new[end_index][0] - a_new[start_index][0]
        results.append((i, j, diff))
        end_index -= 1
    else:
        start_index -= -1

    if start_index == end_index: break

print(results)

Результат:

[(0, 4, 6), (0, 1, 4), (0, 2, 3), (0, 3, 2), (0, 5, 1)]

Вы можете отсортировать массив результатов и получить kth diff.

Answer 3

Вы можете запустить 2 отдельных метода, которые находят максимальное и минимальное значения соответствующих массивов, а затем находят разницу.

ИЛИ

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

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

Answer 4

В псевдокоде это может быть так:

Вы можете отсортировать текущий массив по убыванию, а затем начать вычисления следующим образом:

diffList = {}

calculate(array,k) :

    if (k<=0) OR (array.length < 2) OR (k > 2^(array.length-1))
        return nothing // whatever behavior you want (exception or null Integer whatever suits you)
    else
        return kthLargest(k, 0 , array.length-1, array)
    end if

kthLargest(count, upperBound, lowerBound, array) :
    if count = 0
        if upperBound != lowerBound
            return max(array[upperBound]-array[lowerBound], max(sortDesc(diffList)))
        else
            return max(sort(diffList))
        end if
    else if upperBound = lowerBound
        sortDesc(diffList)
        return diffList[count]
    else
        topDiff = array[upperBound]-array[upperBound+1]
        botDiff = array[lowerBound-1]-array[lowerbound]
        if(topDiff > botDiff)
            add botDiff to diffList
            return kthLargest(count-1,upperBound,lowerBound-1,array)
        else
            add topDiff to diffList
            return kthLargest(count-1,upperBound+1,lowerBound,array)
        end if
    end if

Вызовите метод вычисления (массив, k), и все готово.

Это в основном отслеживает «отброшенную кучу» различий, в то же время повторяя и сокращая границы, чтобы всегда иметь вашу последнюю наибольшую разницу, равную разнице текущих границ или потенциальному лучшему значению в этой отброшенной стопке.

Оба вида (опущены для краткости) должны сделать это O (n log n).

Вы можете заменить массивы на наиболее удобные коллекции и развернуть это также в итеративное решение.

Исправления приветствуются!

Answer 5

Пример на Python

results = []

a = [1,5,4,3,7,2]
a_new = [(1,0), (5,1), (4,2), (3,3), (7,4), (2,5)] #(5,1) -> 5:value and 1:index
sort a_new by value # e.g. mergesort O(nlogn)
start_index = 0
end_index = len(a_new) - 1
i = -1
j = -1
diff = 0

while true: # sequential search
    if(a_new[start_index][1] < a_new[end_index][1]): #compare i and j
        tmp_diff = a_new[end_index][0] - a_new[start_index][0]
        i = start_index
        j = end_index
        diff = tmp_diff
        results.append((I,j,diff)) #add a tuple in results_list
        end_index -= 1
    else: # a_new[start_index][1] > a_new[end_index][1]
        start_index += 1

    if start_index == end_index: break

sort results by diff and return results[k-1]

Надеюсь, это поможет. Я не могу проверить ошибку печати. ​​

Моя идея: максимальная разница -> max_possible_element_value - min_element_value