正整数序列中第k大与第k小之差的计算方法与代码实现

好的，这个问题实际上是一个编程题，我们需要计算序列中第k大的数减去第k小的数的值。 首先，要理解“第k大”和“第k小”的定义： - 第k小：将序列从小到大排序后，位于第k个位置的数（索引从1开始）。 - 第k大：将序列从大到小排序后，位于第k个位置的数（索引从1开始）。 那么，第k大的数其实就是从小到大排序后，位于第 (n - k + 1) 个位置的数（因为第k大等价于第 (n - k + 1) 小）。 我们可以直接对序列进行排序，然后： - 第k小的数 = sorted[k-1]（因为数组索引0~n-1，故索引k-1） - 第k大的数 = sorted[n - k]（因为索引从0开始，第k大即倒数第k个，索引为 n-k） 最终结果 = sorted[n - k] - sorted[k-1] 注意题目保证序列中的数是正整数，且输入不会越界（即k在1和n之间）。 下面我用C++、Python和Java分别来实现。 --- ## 🧮 C++ 实现 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, k; cin >> n >> k; vector<int> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; sort(a.begin(), a.end()); // 第k小（索引k-1），第k大（索引n-k） int ans = a[n - k] - a[k - 1]; cout << ans << endl; return 0; } ``` --- ## 🐍 Python 实现 ```python def main(): n, k = map(int, input().split()) a = list(map(int, input().split())) a.sort() ans = a[n - k] - a[k - 1] print(ans) if __name__ == "__main__": main() ``` --- ## ☕ Java 实现 ```java import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int[] a = new int[n]; for (int i = 0; i < n; ++i) { a[i] = sc.nextInt(); } Arrays.sort(a); int ans = a[n - k] - a[k - 1]; System.out.println(ans); } } ``` --- ## 💡 复杂度分析 - 时间复杂度：O(n log n)，主要来自排序。 - 空间复杂度：O(1)（除输入数组外，没有额外大空间）。 这样我们就完成了题目要求。题目看似简单，但理解第k大与排序索引的关系是关键。 ######[AI问答 | 666点数解答 | 2026-08-07 23:32:30]