获取整数从右数第K位数字

来源: GeeksforGeeks

给定一个整数 N，任务是从其末尾找到第 K 位数字。如果第 K 位不存在，则输出 -1。

示例:

输入: N = 2354, K = 2
输出: 5

输入: N = 1234, K = 1
输出: 4

基本方法: 最直接的方法是将整数 N 转换为字符串，然后根据索引访问。具体步骤如下：

1. 检查 K 是否小于等于 0，如果是，则输出 -1 并返回。
2. 将 N 转换为字符串形式。
3. 如果 K 大于字符串的长度，输出 -1；否则，输出从字符串末尾开始的第 K 个字符。

以下是使用 C++ 实现的基本方法：

#include 
#include 
using namespace std;

void kthDigitFromLast(int n, int k) {
    if (k <= 0) {
        cout <<-1 <        return;
    }
    string temp = to_string(n);
    if (k > temp.length()) {
        cout <<-1 <    } else {
        cout <    }
}

int main() {
    int n = 2354;
    int k = 2;
    kthDigitFromLast(n, k);
    return 0;
}

此外，还可以通过数学运算来解决这个问题，这种方法不需要将整数转换为字符串。具体步骤如下：

1. 检查 K 是否小于等于 0，如果是，则输出 -1 并返回。
2. 不断将 N 除以 10，并减少 K 的值，直到 K 减少到 1 或 N 变为 0。
3. 如果 N 变为 0，输出 -1；否则，输出 N 的最后一位数字（即 N % 10）。

以下是使用 C++ 实现的数学方法：

#include 
using namespace std;

void kthDigitFromLast(int n, int k) {
    if (k <= 0) {
        cout <<-1 <        return;
    }
    while ((k - 1) > 0 && n > 0) {
        n /= 10;
        k--;
    }
    if (n == 0) {
        cout <<-1 <    } else {
        cout <    }
}

int main() {
    int n = 2354;
    int k = 2;
    kthDigitFromLast(n, k);
    return 0;
}

还有一种更高效的解决方案是利用幂函数来计算第 K 位数字。这种方法的时间复杂度较低，适用于较大的 K 值。具体步骤如下：

1. 检查 K 是否小于等于 0，如果是，则输出 -1 并返回。
2. 计算 10^(K-1) 作为除数。
3. 如果除数大于 N，输出 -1；否则，输出 (N / 除数) % 10。

以下是使用 C++ 实现的幂函数方法：

#include 
#include 
using namespace std;

void kthDigitFromLast(int n, int k) {
    if (k <= 0) {
        cout <<-1 <        return;
    }
    int divisor = pow(10, k - 1);
    if (divisor > n) {
        cout <<-1 <    } else {
        cout <<(n / divisor) % 10 <    }
}

int main() {
    int n = 2354;
    int k = 2;
    kthDigitFromLast(n, k);
    return 0;
}

时间复杂度: O(log(K))，其中 K 是要查找的位数。这是因为幂函数计算的时间复杂度为 O(log(K))。

空间复杂度: O(1)，因为所有方法都只使用了常数级的额外空间。