首页 > 试题广场 >

丢失的三个数

[编程题]丢失的三个数

热度指数：31133 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

现在有一个数组，其值为从 1 到 10000 的连续增长的数字。出于某次偶然操作，导致这个数组中丢失了某三个元素，同时顺序被打乱，现在需要你用最快的方法找出丢失的这三个元素，并且将这三个元素根据从小到大重新拼接为一个新数字，计算其除以 7 的余数。例：丢失的元素为336 ，10 ，8435 ，得到的新数字为 103368435 ，除以七的余数为 2 。

输入描述:

输入数据为一行，包含9997个数字，空格隔开。

输出描述:

输出为一行，包含一个数字。

算法知识视频讲解

Java

苏觅云

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        boolean[] fs = new boolean[10001];
        for(int i = 0; i < 9997; i++) {
            fs[sc.nextInt()] = true;
        }
        String ans = "";
        for(int i = 1; i < 10001; i++) {
            if(!fs[i]) {
                ans += i;
            }
        }
        System.out.println(Long.parseLong(ans) % 7);
    }
}

发表于 2022-05-19 22:05:33 回复(0)

Java

重洋

import java.util.*;
import java.math.*;
public class Main{

    public static void main(String[]args){
        Scanner s= new Scanner(System.in);
        int [] numarr =new int[10001];
        
        int count=9997;
        while(count-->0)
            numarr[s.nextInt()]=1;
        
        String str="";
        for(int i=1;i<=10000;i++)
            if(numarr[i]==0)
                str+=String.valueOf(i);
        
        System.out.println( Long.parseLong(str)%7 );
    }
}

发表于 2019-09-10 21:14:02 回复(0)

Java

中南的小菜鸡

import java.util.Scanner;
import java.util.Arrays;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            //创建数组空间10000,
            int[] nums = new int[10000];
            //新数组存丢失的三个元素
            int[] lost = new int[3];
            //输入数据，并排序  nums[0]=1，nums[1]=2,...nums[9999]=10000；
            //输入的数据是无序的，可以利用此方法排序，空缺的元素位置为0
            for(int i=0;i<9997;i++){
                int n = sc.nextInt();
                nums[n-1] = n;
            }
            int j=0;
            //遍历输入的数组，如果数值的值为0，则为丢失的元素，把它并入新数组
            for(int i=0;i<nums.length;i++){
                if(nums[i] == 0){
                    lost[j]=i+1;
                    j++;
                }
            }
            //数组排序
            Arrays.sort(lost);
            //数组作为字符串拼接
            String n = lost[0]+String.valueOf(lost[1])+lost[2];
            //使用Long对象存放数据，Integer可能会溢出（结果可能为12位数）
            System.out.println(Long.valueOf(n) % 7);
        }
    }
}

编辑于 2018-10-10 15:09:45 回复(0)

Java

求知追风

package Test;
import java.math.BigInteger;
import java.util.Scanner;
import java.util.*;
public class Main{
public static void main(String []args){
Scanner sc=new Scanner(System.in);
while(sc.hasNextLine()){
String []str=sc.nextLine().split("\\s");
int arr[]=new int[str.length];
for(int i=0;i<str.length;i++) {
     arr[i]=Integer.valueOf(str[i]);
}
//int a[]=new int[3];
Set<Integer> set=new LinkedHashSet<>();
for(int i=0;i<arr.length;i++) {
     set.add(arr[i]);
}
//
int brr[]=new int[10000];
for(int i=0;i<10000;i++) {
     brr[i]=i+1;
}
//判断
for(int i=0;i<brr.length;i++) {
     set.add(brr[i]);
}
StringBuilder sb=new StringBuilder();
int len=set.size();
int re[]=new int[len];
for(Integer s:set) {
     sb.append(s+" ");
}
String res[]=sb.toString().split(" ");
int ll=res.length;
String c=res[ll-1];
String b=res[ll-2];
String a=res[ll-3];
StringBuilder sb1=new StringBuilder();
String sum=sb1.append(a).append(b).append(c).toString();
if(sum.matches("\\d+")) {
     BigInteger big=new BigInteger(sum);
     System.out.println(big.mod(new BigInteger("7")));

}
}
}

}

算法思想比较好懂，如果大家能够想到set集合不存重复元素这一性质，本题就很好解决了。

为了存取元素顺序的一致，我们使用LinkedHashMap。

首先将输入的9997个数依次存入set集合，然后将1~10000按从小到大的顺序继续存入set集合，由set集合不存取重复元素，所以最终将会把丢失的3个数按从小到大的顺序依次添加到set集合的尾部!

也就是说set集合尾部的3个数就是我们需要的结果（由于使用了LinkedHashMap,保证了存取得一致性）。取出最后3个元素连接起来转换为数字求余即可

发表于 2018-09-07 14:07:12 回复(0)

Java

放学后我不走~

构建一个HashSet或ArrayList集合,将1-10000装进去，然后每输入一个数，就将集合中对应的数remove

最后剩余三个就是就是所谓丢失的数，然后按顺序拼接起来用Long.parseLong(s)转为数字再余7，以防数字过大用Integer.parseInt()出错

代码如下：

import java.util.HashSet;

import java.util.Iterator;
import java.util.Scanner;
public class Main{
public static void main(String[] args){
    Scanner in = new Scanner(System.in);
    HashSet<Integer> hs = new HashSet<Integer>();
    for(int i=1;i<=10000;i++){
        hs.add(i);
    }
    for(int i=0;i<9997;i++){
        int x = in.nextInt();
        hs.remove(x);
    }
    Iterator<Integer> it = hs.iterator();
    String s = "";
    while(it.hasNext()){
        s+=it.next();
    }
    System.out.println(Long.parseLong(s)%7);
}
}

发表于 2018-08-27 00:44:15 回复(0)

Java

AlvinSong

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        boolean[] numExist = new boolean[10000];
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            numExist[sc.nextInt() - 1] = true;
        }
        StringBuilder newNum = new StringBuilder();
        for (int i = 1; i <= 9997; i++) {
            if (!numExist[i - 1])
                newNum.append(i);
        }
        System.out.println(Long.parseLong(newNum.toString()) % 7);
    }
}

使用boolean存储数字是否存在更节省空间。

发表于 2018-07-05 17:36:07 回复(0)

Java

黄小斜

舒服
import java.util.Arrays;
import java.util.Scanner;
public class Main {
     public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int []arr = new int[10001];
        for(int i = 1;i <= 9997;i ++) {
            int n = scanner.nextInt();
            arr[n] = 1;
        }

        int []a = new int[3];
        int j = 0;
        for (int i = 1;i <= 10000;i ++) {
            if (arr[i] == 0) {
                a[j ++] = i;
            }
            continue;
        }
        Arrays.sort(a);
        String s = String.valueOf(a[0]) + String.valueOf(a[1]) + String.valueOf(a[2]);
        long res = Long.parseLong(s);
        System.out.println(res % 7);
    }
}

发表于 2018-06-13 21:38:18 回复(0)

Java

想要offer的小莫

import java.util.*;
public class Main{
public static void main(String []args){
Scanner in=new Scanner(System.in);
int temp;
int []data=new int[10001];
for(int i=0;i<9997;i++){
temp=in.nextInt();
data[temp]=temp;
}
StringBuffer sb=new StringBuffer("");
int flag=0;
for(int i=1;i<=10000;i++){
if(data[i]==0){
sb.append(i);
flag++;
}
if(flag==3){
break;
}
}
System.out.println((Long.parseLong(sb.toString()))%7);
}
}

发表于 2018-04-26 15:00:27 回复(0)

Java

奥利给给起来嗨

import java.util.HashMap;
import java.util.ArrayList;
import java.util.Scanner;
public class Main{
    public static void main(String[] args) {

        ArrayList<String> p = new ArrayList<>();
        int j = 0;
        Scanner sc = new Scanner(System.in);
        HashMap<String, Integer> mp = new HashMap<>();
        StringBuffer sb = new StringBuffer();
            sb = sb.append(sc.nextLine());
        String str = sb.toString();
        String []q = str.split("\\s+");
        for(int i = 0;i < q.length;i++)
        {
            mp.put(q[i], 1);
        }
        for(int i = 1;i < 10001;i++)
        {
            if(mp.get(""+i) == null)
            {
                p.add("" + i);
            }
        }
        String result = p.get(0) + p.get(1) + p.get(2);
        System.out.print(Long.parseLong(result)%7);

    }

}

发表于 2018-04-19 14:06:09 回复(0)

Java

李狗什么

import java.util.*;
public class Main{
public static void main(String[] args){
int[] vals = new int[10001];
int[] newVal = new int[3];
int count = 0;

Scanner sc = new Scanner(System.in);

//存在的数字进行标记

while(sc.hasNext()){
vals[sc.nextInt()] = 1;

}

//减少循环次数直到newVal填充完毕结束，检查未打标记的即为缺省值

for(int i = 1;count<3;i++){
if(vals[i]!=1){
newVal[count]=i;
count++;
}
}
System.out.println(Long.decode(newVal[0]+""+newVal[1]+""+newVal[2])%7);
}
}

编辑于 2018-03-24 14:25:59 回复(0)

Java

七仔0312

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strings = br.readLine().split(" ");
        boolean[] tmp = new boolean[10000];
        for (int i = 0; i < strings.length; i++) {
            int string2int = Integer.parseInt(strings[i]);
            tmp[string2int - 1] = true;
        }
        int index = 0;
        int[] arr = new int[3];
        for (int i = 0; i < 10000; i++) {
            if (tmp[i] != true) {
                arr[index++] = i + 1;
                if (index == 3)
                    break;
            }
        }
        Arrays.sort(arr);
        StringBuilder sb = new StringBuilder();
        sb.append(arr[0]);
        sb.append(arr[1]);
        sb.append(arr[2]);
        long k = Long.parseLong(sb.toString());
        System.out.println(k % 7);

    }
}

发表于 2018-03-18 14:25:48 回复(0)

Java

我是大牛膜拜吧小白

import java.util.ArrayList;
import java.util.Scanner;
public class Main{
public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
     int[] nums=new int[10000];
     ArrayList<Integer> list=new ArrayList<>();
     for(int i=0;i<9997;i++){
         int num=sc.nextInt();
         nums[num-1]=1;
     }
     for(int i=0;i<10000;i++){
         if(nums[i]==0){
             list.add(i+1);
          }    
         if(list.size()==3)break;
     }
     StringBuffer str = new StringBuffer();
     for (int i = 0; i < 3; i++) {
         str.append(list.get(i));
     }
     String numStr = str.toString();
     long newNum = Long.parseLong(numStr);
     System.out.println(newNum%7);
    }
}

编辑于 2018-01-22 20:04:46 回复(0)

Java

星陨无痕

import java.util.*;
import java.math.*;
public class Main{
    //需要的数据空间,因为是1到10000所以需要10001个空间
    static int [] numarr =new int[10001];
    public static void main(String[]args){
        Scanner s= new Scanner(System.in);
        int t=0;
        //去除3个数字后剩余数量9997
        for(int i=0;i<9997;i++){
            t=s.nextInt();
            numarr[t]=1;
        }
        StringBuilder st = new StringBuilder();
        //遍历一次找到数组中为0的数据的下标,就是我们要找的三个数值 
        for(int i=1;i<=10000;i++){
            if(numarr[i]==0){
                st.append(i);
            }
        }
        BigInteger b =new BigInteger(st.toString());
        System.out.println(b.mod(BigInteger.valueOf(7)));
    }
}

编辑于 2018-01-17 17:42:11 回复(3)

Java

傻傻傻傻

//好好读题，注意溢出问题
import java.util.*;
public class Main {
    private final static int count = 9997;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] array = new int[count];
        int[] loss = new int[3];
        for (int i = 0; i < count; i++)
            array[i] = in.nextInt();
        Arrays.sort(array);
        int index = 0;
        for (int i = 0, j = 1; index < 3;) {
            if (array[i] != j ) {
                loss[index++] = j;
                j++;
            } else {
                i++; j++;
            }
        }
        Arrays.sort(loss);
        String res = "" + loss[0] + loss[1] + loss[2];
        System.out.println(Long.parseLong(res) % 7);
    }
}
----------------------------------------------------------------------
//代码改进
import java.util.*;
public class Main {
    private final static int count = 10000;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] array = new int[count + 1];
        int[] loss = new int[3];
        for (int i = 0; i < count - 3; i++)
            array[in.nextInt()] = 1;
        int index = 0;
        for (int i = 1; i <= count; i++) {
            if (array[i] == 0)
                loss[index++] = i;
        }
        Arrays.sort(loss);
        String res = "" + loss[0] + loss[1] + loss[2];
        System.out.println(Long.parseLong(res) % 7);
    }
}
----------------------------------------------------------------------
//再改进
import java.util.*;
public class Main {
    private final static int count = 10000;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] array = new int[count + 1];
        for (int i = 0; i < count - 3; i++)
            array[in.nextInt()] = 1;
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= count; i++) {
            if (array[i] == 0) sb.append(i);
        }
        System.out.println(Long.parseLong(sb.toString()) % 7);
    }
}

编辑于 2017-12-26 09:34:25 回复(0)

Java

初生小牛不怕虎

import java.util.LinkedList; import java.util.Scanner;  public class Main
{ public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);  LinkedList<Integer> n = new LinkedList<>();  StringBuffer sb = new StringBuffer();  int count = 0;  long num;  while (scanner.hasNext()) { for (int i = 0; i < 9997; i++) {
                n.add(scanner.nextInt());  } for (int i = 1; i <=10000; i++) { if (!n.contains(i)) {
                    sb.append(i);  count = count + 1;  if (count == 3) { break;  }
                }
            }
            num = Long.parseLong(sb.toString());  System.out.println(num % 7);  }
    }
}

这题感觉思路理明白了就超简单，就是先把那9997个数存到一个LinkedList里面，然后用LinkedList的contain方法来判断哪些数不在，攒够三个不在的数就跳出循环就可以了

发表于 2017-11-29 19:32:35 回复(0)

Java

指offer的剑在哪？

对输入的数组进行遍历，从1开始，每次与前面的值进行比较，如果刚好等于加1，就continue，如果不等于，就表示当前位置有空缺，就保存res值，最后将res转换成long类型值进行求余即可；

注意：这里一定要转换成long类型，int类型范围不够；

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class StringUtil {
	
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String str[] = bf.readLine().split(" ");
		String res = "";
		for(int i=1; i<str.length; i++){
			int p = Integer.valueOf(str[i-1]);
			int n = Integer.valueOf(str[i]);
			while(p+1 != n){
				res += p+1;
				p++;
			}
		}
	        long resi = Long.valueOf(res)%7;
		System.out.println(resi);
	}
}

发表于 2017-09-12 16:01:43 回复(3)