【LeetCode】215.配列中のK番目の最大要素(JAVA)

原題住所:https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
タイトルの説明:並べ替えられていない配列の中でk番目の最大の要素を見つけます.配列ソート後のk番目の最大要素であり、k番目の異なる要素ではないことに注意してください.
例1:入力:[3,2,1,5,6,4]およびk=2出力:5
例2:入力:[3,2,3,1,2,4,5,5,6]およびk=4出力:4
説明:
kは常に有効であり、1≦k≦配列の長さであると仮定することができます.
解題シナリオ:コード:
カウントソート(最速)

class Solution {
     
    public int findKthLargest(int[] nums, int k) {
     
        int maxNum = 0, minNum = nums[0];
        for(int i = 0; i <nums.length; i ++)
        {
     
            if(nums[i] > maxNum) maxNum = nums[i];
            if(nums[i] < minNum) minNum = nums[i];
        }
        int size = maxNum - minNum + 1;
        int[] numbers = new int[size];
        for(int i = 0; i < nums.length; i ++)
            numbers[nums[i] - minNum] ++;
        int i = size - 1, count = 0;
        for(; i >= 0; i --)
        {
     
            if(count + numbers[i] < k) count += numbers[i];
            else break;
        }
        return i + minNum;
    }
}

ヒープのソート

class Solution {
     
    public int findKthLargest(int[] nums, int k) {
     
        for(int i = 1; i <= k; i ++)
        {
     
            int cur = (nums.length - i) / 2; //        
            while(cur >= 0)
            {
     
                int pos = cur;
                while(pos <= (nums.length - i) / 2)
                {
     
                    int newPos = pos * 2;
                    if(pos * 2 + 1 <= nums.length - i && nums[pos * 2 + 1] > nums[pos * 2])
                        newPos = pos * 2 + 1;
                    if(nums[pos] < nums[newPos])
                    {
     
                        int tmp = nums[newPos];
                        nums[newPos] = nums[pos];
                        nums[pos] = tmp;
                    }
                    else
                        break;
                }
                cur --;
            }
            int tmp = nums[0];
            nums[0] = nums[nums.length - i];
            nums[nums.length - i] = tmp;
        }
        return nums[nums.length - k];
    }
}

泡が立つ

class Solution {
     
    public int findKthLargest(int[] nums, int k) {
     
        for(int i = 1; i <= k; i ++)
        {
     
            for(int j = 0; j < nums.length - i; j ++)
            {
     
                if(nums[j] > nums[j + 1])
                {
     
                    int tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;
                }
            }
        }
        return nums[nums.length - k];
    }
}