[编程题] 查找第 K 大的元素

—

by

FeanLau
in

给定一个无序的整型数组 A [n], 数组大小大于等于 3, 允许有值相同的元素；请设计算法找到该数组排序后第三大的元素值并输出.

输入描述:

一个非空的整数数组 (至少有 3 个元素，可正可负)

输出描述:

第三大的元素值

示例 1

输入 [1,2,3,4,5] 输出 3

示例 2

输入 [1,1,2,2,3] 输出 2

import java.util.PriorityQueue;
import java.util.Scanner;
import static java.lang.Integer.parseInt;
import static java.lang.System.in;
 
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(in);
        String[] str = sc.nextLine().replace("[", "").replace("]", "").split(",");
        int[] data = new int[str.length];
        for (int i = 0; i < data.length; i++) {
            data[i] = parseInt(str[i]);
        }
        System.out.println(findKthNum(data, 3));
        System.out.println(findKthNum1(data, 3));
    }
//方法1，基于快排思想的partion划分，时间复杂度O(n)，空间复杂度O(1)
    public static int findKthNum(int[] data, int k) {
        int begin = 0, end = data.length - 1;
        int pos = 0;
        while (begin <= end) {
            pos = partion(data, begin, end);
            if (pos == k - 1) {
                return data[pos];
            } else if (pos > k - 1) {
                end = pos - 1;
            } else {
                begin = pos + 1;
            }
        }
        return -1;
    }
 
    private static int partion(int[] data, int begin, int end) {
        int temp = data[begin];
        while (begin < end) {
            while (begin < end && data[end] <= temp) {
                end--;
            }
            swap(data, begin, end);
            while (begin < end && data[begin] > temp) {
                begin++;
            }
            swap(data, begin, end);
        }
        return begin;
    }
 
    public static void swap(int[] arr, int i, int j) {
        if (arr == null || i >= arr.length || j >= arr.length || i < 0 || j < 0) {
            return;
        }
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    //方法2，建小顶堆，时间复杂度O(n*logk),空间复杂度O(k)
    public static int findKthNum1(int data[], int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int item : data) {
            if (heap.size() < k) {
                heap.add(item);
            } else if (item > heap.peek()) {
                heap.poll();
                heap.add(item);
            }
        }
        return heap.poll();
    }
}