[Java知识库]O(n)时间复杂度内查找数组中第K大元素

这个题目，是《极客时间》的算法专栏中的一个练习题。我觉着这个题挺有意思，而且感觉也有一定的实战意义。把专栏中的解法摘抄了下来，在ide中运行了一下，运行通过。这个题的意思是这样的。假设有一个数组[2,3,1,7,5,6]，我们要找它的第3大元素，应该是数字3。但是这个题，还有以一个限制，算法的复杂度是O(n)。这就意味着冒泡、直接排序的算法就不行了。这里借鉴了快速排序算法中的分区算法。看一下代码实现

/**
 * search Nth element in array.
 */
public class SearchNthSolution {
    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] arr = new int[]{1, 1, 2};
        System.out.println(searchNth(arr, 2));
    }

    private static int searchNth(int[] arr, int k) {
        if (arr == null || arr.length < k) {
            return -1;
        }
        int partition = partition(arr, 0, arr.length - 1);
        while (partition + 1 != k) {
            if ((partition + 1) < k) {
                partition = partition(arr, partition + 1, arr.length - 1);
            } else {
                partition = partition(arr, 0, partition - 1);
            }
        }
        return arr[partition];
    }

    private static int partition(int[] arr, int p, int r) {
        int pivot = arr[r];
        int i = p;
        for (int j = p; j < r; j++) {
            if (arr[j] <= pivot) {
                swap(arr, i, j);
                i++;
            }
        }
        swap(arr, i, r);
        return i;
    }

    public static void swap(int[] arr, int i, int j) {
        if (i == j) {
            return;
        }
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

其实，这个代码没啥好讲的，核心逻辑就是分区函数的实现。大家对分区函数的实现原理有兴趣，可以先看一下我写的这一篇快速排序，我简单介绍了一下分区函数的作用及实现。说回到这篇文章，主要就是利用的分区函数每次返回的partitiion值，其实就是下一次分区的pivot索引，也是已排序区间的最大值所在的索引。partition的值如果等于k，则arr[partition]就是我们要找的当前数组的第k大的元素。这个算法的思路，非常巧妙，要好好理解一下。