关于算法-数据结构:PAT甲级1048-Find-Coins

题目粗心：

给出n个正整数和一个正整数m,问n个数字中是否存在一对数字a和b(a$\leq$b),使得a+b=m成立。如果有多对，输入a最小的那一对。

算法思路1：

应用hash散列的思维来解决每一个输出的数字，nums来记录每一个数字呈现的次数，下标为数字，其值为呈现次数。那么咱们从0开始遍历始终到1000，对于每一个数字j,首先得判断j和M-j呈现的次数是否都不为0，如果是，对于所有j!=M-j(两数字不相等)或者j==M-j并且nums[j]>1(两数字相等然而呈现了至多2次)，就输入j和M-j，并且完结程序即可。如果遍历结束，输入No Solution

算法思路2：

应用二分查找的思维解决该问题，首先，应用coins数组存储所有的货币，而后对其从小达到排序，遍历每一个coins[j],在数组中查找M-coins[j]，如果存在，并且其地位pos不等于j,就输入coins[j]和M-coins[j],并且退出循环。如果遍历结束，输入No Solution.

算法思路3：

同样应用coins数组存储所有的货币，而后对其从小达到排序。而后应用指针i指向0,指针j指向N-1,而后i向右走，j向左走，如果i和j指向的数字之和sum等于M，就输入coins[i]和coins[j]而后完结程序，如果sum<M,阐明coins[i]太小，那么就让i向右走一格，否则说coins[j]太大，就让j向左走一格。如果遍历结束，输入No Solution

留神点：

1、得将nums数组写在main函数里面，不然测试点1报错。
2、得思考2个数字相等的状况，不然测试点1报错。
3、二分法的二分函数得写在main函数外，不然测试点1和2会运行超时。
4、集体举荐算法思路3，无需思考2个数字相等

提交后果：

AC代码1：

#include <cstdio>

using namespace std;

int nums[1001];// 得写在main函数里面
int main()
{
    int N,M;
    scanf("%d %d",&N,&M);
    int temp;
    for (int i = 0; i < N; ++i) {
        scanf("%d",&temp);
        ++nums[temp];
    }
    for (int j = 0; j < 1001; ++j) {
        if(nums[j]!=0&&nums[M-j]!=0){
            if(j!=M-j||(2*j==M&&nums[j]>1)){
                printf("%d %d",j,M-j);
                return 0;
            }
        }
    }
    printf("No Solution");
    return 0;
}

AC代码2：

#include <cstdio>
#include <algorithm>

using namespace std;

int binarySearch(int left,int right,int num,const int coins[]){
    int mid;
    while (left<=right){
        mid = left + (right-left)/2;
        if(coins[mid]==num){
            return mid;
        } else if (coins[mid]<num){
            left = mid+1;
        } else {
            right = mid-1;
        }
    }
    return -1;
}

int main(){
    int N,M;
    scanf("%d %d",&N,&M);
    int coins[N];
    for(int i=0;i<N;++i){
        scanf("%d",&coins[i]);
    }
    sort(coins,coins+N);
    for (int j = 0; j < N; ++j) {
        //对于coins[j],查找M-coins[j]==coins[k]的k并且k!=j
        int mid;
        int pos = binarySearch(0,N-1,M-coins[j],coins);
        if(pos!=-1&&pos!=j){
            printf("%d %d",coins[j],coins[pos]);
            return 0;
        }
    }
    printf("No Solution");
    return 0;
}

AC代码3：

#include <cstdio>
#include <algorithm>

using namespace std;

int main(){
    int N,M;
    scanf("%d %d",&N,&M);
    int coins[N];
    for(int i=0;i<N;++i){
        scanf("%d",&coins[i]);
    }
    sort(coins,coins+N);
    int i=0,j=N-1;
    while (i<j){
        if(coins[i]+coins[j]==M){
            printf("%d %d",coins[i],coins[j]);
            return 0;
        } else if(coins[i]+coins[j]<M){
            ++i;
        } else {
            --j;
        }
    }
    printf("No Solution");
    return 0;
}