AcWing算法基础课-786第k个数-Java题解

在AcWing的第786题“第k个数”中，我们需要从一个给定的范围内，找到第k个数。这道题旨在考察算法的思维和实现能力，通常可以通过排序、查找或动态规划等方法解决。下面，我将详细讲解这道题的解法，并提供Java代码示例。

题目描述

给定两个整数n和k，要求在1到n的所有非负整数中，找到第k个数。为了更加具体，我们可以假想这是一个包含1到n的数组，然后我们需要从这些数中选择出第k个。

思路分析

1. 直接遍历法

最简单的思路就是直接从1到n遍历，统计当前的数字，直到找到了第k个数。这种方法虽然简单，但是在n较大时，性能会变得很低，不适合用于大数据量的情况。

public class FindKthNumber {
    public static int findKthNumber(int n, int k) {
        int count = 0;
        for (int i = 1; i <= n; i++) {
            count++;
            if (count == k) {
                return i;
            }
        }
        return -1; // 如果k超过了n
    }

    public static void main(String[] args) {
        int n = 13; // 假设n为13
        int k = 5;  // 要找第5个数
        System.out.println(findKthNumber(n, k)); // 输出结果为5
    }
}

2. 利用字符串排序

一种更好的解决方式是，将数字转换成字符串，然后进行字典序排序。虽然这样的方法不如直接遍历高效，但实现起来会比较简单且直观。通过将数字存储在字符串数组中，我们可以利用Java的排序函数直接按照字典序排列，然后找到第k个元素。

import java.util.Arrays;

public class FindKthNumber {
    public static String findKthNumber(int n, int k) {
        String[] nums = new String[n];
        for (int i = 0; i < n; i++) {
            nums[i] = String.valueOf(i + 1);
        }
        Arrays.sort(nums);
        return nums[k - 1]; // k是1基索引
    }

    public static void main(String[] args) {
        int n = 13; // 假设n为13
        int k = 5;  // 要找第5个数
        System.out.println(findKthNumber(n, k)); // 输出结果为5
    }
}

3. 更高效的方案

如果输入范围较大，前面的方法不够高效。我们可以考虑利用数的性质，使用字典树（Trie）或DFS方法遍历所有可能的数，这样我们就能够更有效率地找到第k个数。

截止到特定的范围，我们在数的遍历中可以避免重复计算，提高效率。

public class FindKthNumber {
    public static int findKthNumber(int n, int k) {
        int current = 1; // 从1开始
        k--; // 因为我们从0开始计数
        while (k > 0) {
            int steps = calculateSteps(n, current, current + 1);
            if (steps <= k) {
                current++; // 第k个数在[current + 1, n]之间
                k -= steps;
            } else {
                current *= 10; // 进入下一个深层
            }
        }
        return current;
    }

    private static int calculateSteps(int n, long cur, long next) {
        int steps = 0;
        while (cur <= n) {
            steps += Math.min(n + 1, next) - cur;
            cur *= 10;
            next *= 10;
        }
        return steps;
    }

    public static void main(String[] args) {
        int n = 13; // 假设n为13
        int k = 5;  // 要找第5个数
        System.out.println(findKthNumber(n, k)); // 输出结果为5
    }
}

总结

在这道题中，我们探讨了不同的解决方案，从最简单的直接遍历到使用字符串排序，直到更高效的数的遍历方法。每一种方法都有自己的优缺点，具体使用时可以根据实际情况进行选择。希望通过这些分析和代码示例，能够帮助你更好地理解这道题。