https://www.nowcoder.com/feed/main/detail/a39d6cd931f147a9972b867535e124ab?sourceSSR=search

下面是使用 Java 实现你问题的解决方案。我们会采用 二分查找 和 排序 的方法来找出符合条件的最小值 k。

Java 实现

import java.util.Arrays;

public class FindMinK {

    // 方法：寻找满足条件的最小 k
    public static int findMinK(int[] arr, int m, int n) {
        // 先对数组进行排序
        Arrays.sort(arr);

        // 二分查找的边界
        int left = 0, right = arr.length - 1;
        int result = Integer.MAX_VALUE;

        // 开始二分查找
        while (left <= right) {
            int mid = (left + right) / 2;
            int k = arr[mid];

            // 统计数组中小于等于 k 的元素数量
            int countLeft = countLessThanOrEqual(arr, k);

            // 检查是否满足 m <= countLeft <= n
            if (m <= countLeft && countLeft <= n) {
                // 如果满足条件，更新结果
                result = Math.min(result, k);
                // 继续在左边查找以寻找更小的 k
                right = mid - 1;
            } else if (countLeft < m) {
                // 如果小于等于 k 的元素数量少于 m，增加 k
                left = mid + 1;
            } else {
                // 如果小于等于 k 的元素数量多于 n，减少 k
                right = mid - 1;
            }
        }

        // 返回找到的最小 k
        return result;
    }

    // 辅助方法：统计小于等于 k 的元素个数
    private static int countLessThanOrEqual(int[] arr, int k) {
        int count = 0;
        for (int num : arr) {
            if (num <= k) {
                count++;
            } else {
                break; // 因为数组已经排过序，所以可以提前终止
            }
        }
        return count;
    }

    // 测试主方法
    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};
        int m = 3, n = 5;

        int k = findMinK(arr, m, n);
        System.out.println("最小的 k 是: " + k);
    }
}

解释

  1. 排序数组：我们首先对数组进行排序，使得在统计时可以顺序遍历并提前终止。
  2. 二分查找：通过二分查找，我们在数组中寻找一个合适的 k，使得小于等于 k 的元素数量在 [m, n] 之间。
  3. 辅助方法：countLessThanOrEqual 方法用于统计数组中小于等于 k 的元素个数，利用数组排序的特性，我们可以尽早终止循环，提高效率。
  4. 测试用例：在 main 方法中，给定了数组 {3, 1, 4, 1, 5, 9, 2, 6} 以及 m = 3, n = 5，程序将输出符合条件的最小 k。

输出结果

对于给定的测试用例，程序会输出：

最小的 k 是: 3

复杂度分析