算法——寻找第K个最大的数

在未排序的数组中找到第 k 个最大的元素。
链接: leetcode.

解题思路：通过快速排序的思想方法，每次随机获取指定范围内一个树的排序位置，然后根据这个位置，再重新指定范围，直到这个位置索引满足K。

class Solution {

    public int findKthLargest(int[] nums, int k) {

        int n = nums.length;

        int left = 0, right = n - 1;

        // 将数组分为两个部分，获取一个正确序号的位置

        int index = part(nums, left, right);

        k = n - k;

        while(index != k) {

            if(index > k) {

                right = index - 1;

            }else {

                left = index + 1;

            }

            index = part(nums, left, right);

        }

        return nums[k];

    }

    public int part(int[] nums, int l, int r) {

        if(l >= r) return l;

        int i = l, j = r;

        // 选取第一个数为比较值

        int x = nums[l];

        while(i != j) {

        	// 这里需要让j先--，因为必须保证i的数值是在正确的位置。

            while(i < j && nums[j] > x) j--;

            while(i < j && nums[i] <= x) i++;

            if(i < j) swap(nums, i, j);

        }

        // 将比较值放到正确的位置

        nums[l] = nums[i];

        nums[i] = x;

        // 范围比较值的排序位置

        return i;

    }

    public void swap(int[] nums, int i, int j) {

        int temp = nums[i];

        nums[i] = nums[j];

        nums[j] = temp;

    }

}

巴特西

算法——寻找第K个最大的数

最新文章

热门文章