Search Number 科研调查时得到了n个自然数，每个数均不超过1500000000。已知不相同的数不超过10000个...

### Search Number 问题解析 #### 问题描述 本题是一道经典的查找问题，涉及到的数据规模为：科研调查中获得了一系列的自然数（总数为n），这些数字都不超过1500000000，并且不同的数字不会超过10000个。题目要求在这些数字中查找特定的自然数x，如果找到了，则输出该数字及其出现的次数；如果未找到，则输出NO。 #### 输入格式 输入由多组测试数据组成。每组测试数据包括： 1. 第一行：两个整数n和x，其中n表示自然数的个数，x表示要查找的自然数。 2. 接下来n行：每行一个自然数。 #### 输出格式 对于每组输入，如果找到了x，则输出该自然数及其出现的次数；如果未找到，则输出NO。 #### 样例输入输出 ``` 样例输入： 8 100 2 4 2 4 5 100 2 100 8 3 2 4 2 4 5 100 2 100 样例输出： 100 2 NO ``` #### 解决方案分析 本题的关键在于高效地完成查找任务。考虑到数据的特点，即不相同的数字最多只有10000个，我们可以采用以下几种方法： 1. **暴力法**：遍历整个数组，统计目标数字的出现次数。这种方法简单直观，但效率较低，时间复杂度为O(n)。 2. **排序+二分查找**：首先对数组进行排序，然后通过二分查找定位目标数字，并统计其出现次数。这种方法的时间复杂度为O(n log n) + O(log n)，适用于数据量较大且要求较快响应速度的情况。 3. **哈希表**：利用哈希表记录每个数字出现的次数。这种方法的时间复杂度为O(n)，适用于快速查询，尤其是当不相同数字较少时更为有效。 #### 示例代码解析 示例代码采用了排序+二分查找的方法实现。 1. **输入处理**：读取输入的n和x以及随后的n个自然数，并存储到数组`a`中。 2. **排序**：使用快速排序算法对数组`a`进行排序。 3. **查找**：遍历排序后的数组，统计目标数字x的出现次数。 4. **输出结果**：根据统计的结果输出对应的答案。 #### 代码详解 ```cpp #include<stdio.h> #include<string.h> #define LEN 200000 // 定义数组长度 int a[LEN], temp, mid; // 快速排序的分区函数 int sort(int *a, int low, int high) { mid = a[low]; while (low < high) { while (low < high && a[high] >= mid) high--; // 找到小于mid的元素 temp = a[low]; a[low] = a[high]; a[high] = temp; // 交换元素 while (low < high && a[high] <= mid) low++; // 找到大于mid的元素 temp = a[low]; a[low] = a[high]; a[high] = temp; // 交换元素 } return low; } // 快速排序函数 void quicksort(int *a, int low, int high) { if (low < high) { mid = sort(a, low, high); // 分区 quicksort(a, low, mid - 1); // 对左半部分递归排序 quicksort(a, mid + 1, high); // 对右半部分递归排序 } } int main() { int i, n, s; int Sum = 0; scanf("%d", &n); scanf("%d", &s); for (i = 0; i < n; i++) { scanf("%d", &a[i]); } quicksort(a, 0, n - 1); // 排序 for (i = 0; i < n; i++) { // 统计次数 if (a[i] == s) { Sum++; } } if (Sum == 0) { printf("NO\n"); } else { printf("%d %d\n", s, Sum); } return 0; } ``` #### 总结 通过对本题的分析与解决，我们可以了解到几种不同的查找方法及其适用场景。在实际应用中，应根据具体的数据特点选择合适的算法以达到最优效果。对于本题来说，由于数据量适中且不相同数字数量有限，采用排序+二分查找或哈希表的方法都是比较好的选择。