51nod --1001 数组中和等于K的数对(一级算法题)

1001 数组中和等于K的数对


基准时间限制:1 秒 空间限制:131072 KB 分值: 5 难度:1级算法题 收藏 关注
给出一个整数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


个人解题思路

/*
个人解题思路:由于观察数据量50000,可知(n2)的复杂度,肯定会超时,于是想到了(nlogn),便想到了二分,于是,便想到了a+b=k;那么b=k-a;又由于输出条件要从小到大,便想到了排序,
刚好二分查找也要求有序,于是问题:便变成了,从一个有序数组查找一个数
*/

代码


import java.util.*;
public class Main{
    static int n;
    static int index =0; //记录要查找那个数的下标
    //为什么要找他下标呢?因为用过一次的就要记录下来,下次不能要用了
    static int[] arr = null;
    static int[] vis = null;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        n = sc.nextInt();
        arr = new int[n];
        vis = new int[n];
        //input
        for(int i=0; i<n; ++i)
            arr[i] = sc.nextInt();
        //process
        Arrays.sort(arr);
        boolean flag = false;
        for(int i=0; i<n; ++i)
        if(vis[i] == 0){
            vis[i] = 1;
            int res = k - arr[i];
            boolean tag = find_res(res,i);
            if(tag){
                System.out.println(arr[i] + " " + res );
                vis[index] = 1;
                flag = true;
            }
            else
                continue;
        }
        if(flag == false)
            System.out.println("No Solution");
    }
    public static boolean find_res(int num, int in){
        int i = 0;
        int j = n-1;
        int mid = 0;
        boolean tag = false;
        while(i <= j){
            mid = i + (j-i)/2;
            if(arr[mid] < num){
                i = mid + 1;
            }else if(arr[mid] > num){
                j = mid - 1;
            }else{
                index = mid;
                tag = true;
                break;
            } 
        }
        if(tag == true && in != index) //去掉相同的,比如8=4+4,但是4只有一个的情况
            return true;
        return false;
    }
}
全部评论

相关推荐

昨天 11:33
江南大学 Java
已经在暑假实习了&nbsp;,没有明确说有hc,纠结实习到八月份会不会有点影响秋招毕竟感觉今年好多提前批
程序员小白条:92的话准备提前批,其他没必要,没面试机会的,而且你要准备充分,尤其八股和算法题
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 11:35
程序员小白条:话太多,没实力和学历,差不多回答回答就行了,身份地位不一样
点赞 评论 收藏
分享
水墨不写bug:疑似没有上过大学
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-02 17:28
25届每天都在焦虑找工作的事情0offer情绪一直很低落硬撑着面了一个岗位岗位有应酬的成分面试的时候hr给我出各种场景题问的问题比较犀利&nbsp;有点压力面的感觉感觉有点回答不上来本来就压抑的情绪瞬间爆发了呢一瞬间特别想哭觉得自己特别没用没绷住掉眼泪了事后想想觉得自己挺有病的&nbsp;真的破大防了
喜欢唱跳rap小刺猬...:我觉得没关系吧,之前有一次面试leader给我压力面,我顶住了压力,结果入职的时候发现组里氛围很差,果断跑路。其实从面试就能大概看出组的情况,面试体验好的组倒是不一定好,但是面试体验不好的组。。。就很难说
面试尴尬现场
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务