面试算法76:数组中第k大的数字

发布时间:2023年12月28日

题目

请从一个乱序数组中找出第k大的数字。例如,数组[3,1,2,4,5,5,6]中第3大的数字是5。

分析

面试题59中介绍过一种基于最小堆的解法。这种解法的数据位于一个数据流中,不能一次性地将所有数据全部读入内存。而本题不一样,数据都保存在一个数组中,所有操作都在内存中完成。我们有更快找出第k大的数字的算法。在长度为n的排序数组中,第k大的数字的下标是n-k。下面用快速排序的函数partition对数组分区,如果函数partition选取的中间值在分区之后的下标正好是n-k,分区后左边的值都比中间值小,右边的值都比中间值大,即使整个数组不是排序的,中间值也肯定是第k大的数字。

public class Test {
    public static void main(String[] args) {
        int[] nums = {3, 1, 2, 4, 5, 5, 6};
        int result = findKthLargest(nums, 3);
        System.out.println(result);
    }

    public static int findKthLargest(int[] nums, int k) {
        int target = nums.length - k;
        int start = 0;
        int end = nums.length - 1;
        int index = partition(nums, start, end);
        while (index != target) {
            if (index > target) {
                end = index - 1;
            }
            else {
                start = index + 1;
            }
            
            index = partition(nums, start, end);
        }

        return nums[index];
    }

    public static int partition(int[] nums, int start, int end) {
        int pivot = new Random().nextInt(end - start + 1) + start;
        swap(nums, pivot, end);

        int small = start - 1;
        for (int i = start; i < end; i++) {
            if (nums[i] < nums[end]) {
                small++;
                swap(nums, i, small);
            }
        }
        small++;
        swap(nums, small, end);

        return small;
    }

    public static void swap(int[] nums, int index1, int index2) {
        if (index1 != index2) {
            int temp = nums[index1];
            nums[index1] = nums[index2];
            nums[index2] = temp;
        }
    }
}
文章来源:https://blog.csdn.net/GoGleTech/article/details/135275764
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。