51Nod--1001 数组中和等于K的数对

我不是女神ヾ 2022-06-15 09:44 106阅读 0赞

题目链接：[http://www.51nod.com/onlineJudge/questionCode.html\#!problemId=1001][http_www.51nod.com_onlineJudge_questionCode.html_problemId_1001]

给出一个整数K和一个无序数组A，A的元素为N个互不相同的整数，找出数组A中所有和等于K的数对。例如K = 8，数组A：\{-1,6,5,3,4,2,9,0,8\}，所有和等于8的数对包括(-1,9)，(0,8)，(2,6)，(3,5)。  
Input  
第1行：用空格隔开的2个数，K N，N为A数组的长度。(2 <= N <= 50000，-10^9 <= K <= 10^9)  
第2 - N + 1行：A数组的N个元素。（-10^9 <= A\[i\] <= 10^9)  
Output  
第1 - M行：每行2个数，要求较小的数在前面，并且这M个数对按照较小的数升序排列。  
如果不存在任何一组解则输出：No Solution。  
Input示例  
8 9  
\-1  
6  
5  
3  
4  
2  
9  
0  
8  
Output示例  
\-1 9  
0 8  
2 6  
3 5

这道题最直观的的解法就是用一个双重循环，逐步枚举，但是想想时间复杂度为O(n^2)，肯定 timeout。  
更聪明一点的做法就是先对数组升序排序，然后对于每个数字，使用二分查找另外一个和气匹配的数字。这样做的时间复杂度为O(n\*log(n))，下面是代码：

#include <stdio.h>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int N = 50010;
    int a[N];
    
    // 二分查找： 
    int binarySearch(int a[], int start, int end, int value) {
        if(start >= end) {
            return -1;
        }
        int mid = (start + end)/2;
        if(a[mid] == value) {
            return mid; 
        } else if(a[mid] > value) {
            binarySearch(a, start, mid, value);
        } else {
            binarySearch(a, mid+1, end, value);
        }
    }
    
    int main() {
        int k, n;
        bool res = false;
        cin >> k >> n;
        for(int i = 0 ; i < n; i++) {
            scanf("%d", a+i);
        } 
        // 对数据从小到大排序 
        sort(a, a+n);
        int maxIndex = n; 
        for(int i = 0; i < n; i++) {
            // 从当前下标+1开始搜素数组元素，是否存在满足条件的数字 
            int jud = binarySearch(a, i+1, maxIndex, k-a[i]);
            if(jud != -1) {
                // 找到了就输出。 
                printf("%d %d\n", a[i], a[jud]);
                /**
                 * 更新最大数组下标，因为排序后数据是升序的，
                 * 下一个数字肯定比现在的数字大，那么与其匹配的数字就要更小，
                 * 其下标即为在当前找到的数字下标之前
                 */ 
                maxIndex = jud;
                res = true;
            } 
        }
    
        if(!res) {
            printf("No Solution\n");
        }
    
        return 0;
    }

[http_www.51nod.com_onlineJudge_questionCode.html_problemId_1001]: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1001