首页 > 360笔试 第一题. 跪求大佬指教. 应该是O(n)也超时么
头像
牛客404715914号
编辑于 2020-09-12 17:31
+ 关注

360笔试 第一题. 跪求大佬指教. 应该是O(n)也超时么

理论上我代码应该是O(n), 为什么只过55% 剩余全部超时呢?
我想的是: 先把所有ID都列出来. 然后在读取的时候, 把第一条和最后一条留着最后处理, 中间所有打卡的ID都不可能是老板, 指教从list中移除
读取到最后一条后判断第一条和最后一条: 1. 如果两个ID相同, 则老板可能是这个. 2. 如果ID不同, 第二位数也不同(0和1). 则老板也不可能是. 3. ID不同, 第二位数都是(1), 则排除第一位. 4. ID不同, 第二位都是(0), 则直接排除最后一个.
难道是还有情况没有考虑到吗? 求指教. 感谢
public static void main(String args[]){
		Scanner scan = new Scanner(System.in);
        String[] temp = scan.nextLine().split(" ");
        int n = Integer.parseInt(temp[0]);
        int m = Integer.parseInt(temp[1]);
        List<Integer> possible = new ArrayList<>();
        for(int a = 0; a < n; a++) {
        	possible.add(a+1);
        }
        
        int count = 0;
        int[] first = new int[2];
        while(count < m){
            temp = scan.nextLine().split(" ");
            if(count == 0) {
            	first[0] = Integer.parseInt(temp[0]);
            	first[1] = Integer.parseInt(temp[1]);
            	count++;
            	continue;
            }
            if(count == m-1) {
            	if(first[1] == Integer.parseInt(temp[1])) {
            		if(first[1] == 0) possible.remove(new Integer(first[0]));
            		else possible.remove(new Integer(Integer.parseInt(temp[0])));
            	}else {
            		if(first[0] != Integer.parseInt(temp[0])) {
            			possible.remove(new Integer(Integer.parseInt(temp[0])));
            			possible.remove(new Integer(first[0]));
            		}
            	}
            	break;
            }
            possible.remove(new Integer(Integer.parseInt(temp[0])));
            count++;
        }
        for(Integer a: possible) System.out.print(a+" ");
    }


全部评论

(0) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐