给定一系列正整数，请设计一个尽可能高效的算法，查找倒数第k个位置上的数字

假设给定的正整数序列为a1, a2, ..., an，倒数第k个位置指的是从序列末尾往前数第k个位置，也就是第n-k+1个位置。

一种简单的做法是先遍历一遍序列，确定序列的长度n，然后再遍历一遍序列找到第n-k+1个位置的数。这种做法的时间复杂度为O(n)，并不是最优的。

更高效的做法是使用双指针。首先让一个指针p1从序列开头向前移动k-1个位置，然后再让另一个指针p2从序列开头开始和p1一起向前移动，直到p1到达序列末尾为止。此时p2所指的位置就是倒数第k个位置。这种做法的时间复杂度为O(n)，但是实际上只需要遍历一次序列，所以速度会比上一种做法快很多。

相关问题

给定一系列正整数，请设计一个尽可能高效的算法，查找倒数第K个位置上的数字。

算法思路：

1.先求出给定正整数的位数n。

2.倒数第K个位置上的数字即为正数第n-K+1个位置上的数字。

3.将给定正整数从左往右数的每一位数字存入一个数组中。

4.输出数组中第n-K+1个位置上的数字即可。

算法实现：

C++代码如下：

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> nums(n);
    for(int i = 0; i < n; i++)
        cin >> nums[i];
    cout << nums[n-k] << endl;
    return 0;
}

Python代码如下：

n, k = map(int, input().split())
nums = list(map(int, input().split()))
print(nums[n-k])

C语言 给定一系列正整数，请设计一个尽可能高效的算法，查找倒数第K个位置上的数字。

算法思路：

1.定义一个计数器count，用来记录已经遍历的正整数的个数。

2.从第一个正整数开始遍历，每遍历一个正整数，count自增1。

3.当count等于K时，记录当前遍历到的正整数的值。

4.继续遍历，直到遍历完所有正整数。

5.返回记录的正整数的值。

算法实现：

#include <stdio.h>

int findKthDigit(int* nums, int numsSize, int k) {
    int count = 0;
    int i;
    for (i = 0; i < numsSize; i++) {
        int num = nums[i];
        while (num > 0) {
            count++;
            if (count == k) {
                return num % 10;
            }
            num /= 10;
        }
    }
    return -1;
}

int main() {
    int nums[] = {123, 456, 789};
    int numsSize = 3;
    int k = 7;
    int digit = findKthDigit(nums, numsSize, k);
    printf("%d\n", digit);
    return 0;
}

算法分析：

时间复杂度：O(nm)，其中n是正整数的个数，m是正整数的位数。因为要遍历所有的正整数，对于每个正整数，需要遍历它的每一位，所以时间复杂度是O(nm)。

空间复杂度：O(1)，算法只使用了常数个额外的变量。