时间戳

首页 > 解决方案 > 如何找到 int[] 中的第 K 个最大差异？

java - 如何找到 int[] 中的第 K 个最大差异？

问题描述

我有一个算法问题。

例如，有一个int[]像[1,5,4,3,7,2].

我想在这个数组中找到第 k 个最大的差异，例如：

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

（索引 i 必须小于j且array[i]必须大于array[j]）。

输出是j在这个问题中返回。

我目前的想法：

但时间复杂度为O(n^2)。

有更好的解决方案吗？

标签： javaarraysalgorithmtime

解决方案

伪代码方面，它可以这样：

您可以对当前数组进行降序排序，然后像这样开始计算：

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

调用 calculate(array,k) 就可以了。

这基本上可以跟踪“丢弃的一堆”差异，同时迭代和减少边界以始终使最终最大差异是当前边界的差异或该丢弃堆中的潜在更好值。

两种类型（为简洁起见省略）都应该使这个 O(n log n)。

您可以将数组替换为最方便的集合，并将其展开为迭代解决方案。

更正赞赏！

推荐阅读