Java数组中查找第k个最大与最小元素的问题求助

我需要在Java数组中查找第k个最大和最小元素，当前实现处理带重复元素的数组时出现了问题：

当数组为{5, 1, 8, 5, 9, 8, 0}，查找第3个最小和最大元素时，程序输出5 8，但正确结果应该是5 5。我不想去除数组中的重复元素，希望得到解决办法。

我的当前实现代码：

package Arrays;
import java.util.Arrays;
public class KthSmallestAndLargestArray {
    static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    static void KthSmallLargeArrayUsingLogic(int[] arr) {
        int temp=0;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        System.out.println("Sorted Array:");
        printArray(arr);
        System.out.println("Kth Smallest and Largest values using logic are:");
        System.out.println(arr[2]+" "+arr[arr.length-3]);
    }
    static int[] SmallestLargestArrayUsingFunction(int[] arr){
        Arrays.sort(arr);
        int[] ans={arr[0],arr[arr.length-1]};
        System.out.println(arr[2]+" "+arr[arr.length-3]);
        return ans;
    }
    public static void main(String[] args) {
        int[] arr = { 5, 1, 8, 5, 9, 8, 0 };
        System.out.println("Orignal Array:");
        printArray(arr);
        KthSmallLargeArrayUsingLogic(arr);
        System.out.println("Kth Smallest and Largest values using function are:");
        SmallestLargestArrayUsingFunction(arr);
    }
}

问题原因 #

你当前的实现是直接对数组排序后，通过索引位置获取元素：排序后的数组是[0,1,5,5,8,8,9]，取索引2（第3个位置）得到5，取索引7-3=4得到8。但这是按“排序后的位置”取元素，而不是按“元素的排名”取——你想要的是第3个不同排名的元素：

• 第1小：0，第2小：1，第3小：5
• 第1大：9，第2大：8，第3大：5

解决方案 #

下面提供几种不需要去重数组的实现方式：

方法1：遍历排序后的数组，跳过重复元素计数

排序后，遍历数组，每遇到一个新的不同元素就计数，直到计数到k，即为目标元素。

示例实现：

// 找第k小的元素（k从1开始）
static int findKthSmallestWithDuplicates(int[] arr, int k) {
    Arrays.sort(arr);
    int count = 1;
    int prev = arr[0];
    if (k == 1) return prev;
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] != prev) {
            count++;
            prev = arr[i];
            if (count == k) {
                return arr[i];
            }
        }
    }
    // 如果k超过不同元素的数量，返回最后一个元素（根据需求调整）
    return arr[arr.length - 1];
}

// 找第k大的元素（k从1开始）
static int findKthLargestWithDuplicates(int[] arr, int k) {
    Arrays.sort(arr);
    int count = 1;
    int prev = arr[arr.length - 1];
    if (k == 1) return prev;
    for (int i = arr.length - 2; i >= 0; i--) {
        if (arr[i] != prev) {
            count++;
            prev = arr[i];
            if (count == k) {
                return arr[i];
            }
        }
    }
    return arr[0];
}

修改main方法调用：

public static void main(String[] args) {
    int[] arr = { 5, 1, 8, 5, 9, 8, 0 };
    int k = 3;
    System.out.println("Original Array:");
    printArray(arr);
    
    int kthSmall = findKthSmallestWithDuplicates(arr.clone(), k);
    int kthLarge = findKthLargestWithDuplicates(arr.clone(), k);
    System.out.println("第" + k + "小元素：" + kthSmall);
    System.out.println("第" + k + "大元素：" + kthLarge);
}

注意：使用arr.clone()避免修改原数组。

方法2：使用TreeSet去重并排序

TreeSet会自动对元素排序并去重，我们可以直接获取第k个元素：

import java.util.TreeSet;

static int findKthSmallestUsingTreeSet(int[] arr, int k) {
    TreeSet<Integer> set = new TreeSet<>();
    for (int num : arr) {
        set.add(num);
    }
    // 获取第k个元素（TreeSet的迭代器按升序排列）
    int count = 1;
    for (int num : set) {
        if (count == k) {
            return num;
        }
        count++;
    }
    return -1; // 处理k超出范围的情况
}

static int findKthLargestUsingTreeSet(int[] arr, int k) {
    TreeSet<Integer> set = new TreeSet<>();
    for (int num : arr) {
        set.add(num);
    }
    // 获取倒数第k个元素
    int count = 1;
    for (int num : set.descendingSet()) {
        if (count == k) {
            return num;
        }
        count++;
    }
    return -1;
}

测试结果 #

使用上述方法，对于数组{5,1,8,5,9,8,0}，第3小元素是5，第3大元素是5，符合预期。

内容的提问来源于stack exchange，提问作者Prabhjyot Singh