[编程题]丢失的三个数
- 热度指数：31129 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
现在有一个数组，其值为从 1 到 10000 的连续增长的数字。出于某次偶然操作，导致这个数组中丢失了某三个元素，同时顺序被打乱，现在需要你用最快的方法找出丢失的这三个元素，并且将这三个元素根据从小到大重新拼接为一个新数字，计算其除以 7 的余数。 例：丢失的元素为336 ，10 ，8435 ，得到的新数字为 103368435 ，除以七的余数为 2 。
输入描述:
输入数据为一行，包含9997个数字，空格隔开。
输出描述:
输出为一行，包含一个数字。
舒服
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)
更多回答
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)
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
public static void main(String[] args) {
int[] integers = new int[10001];
Scanner in = new Scanner(System.in);
for (int i = 1; i <= 9997; i++) {
int temp = in.nextInt();
integers[temp] = temp;
}
ArrayList<Integer> lostIntegers = new ArrayList<Integer>();
for (int i = 1; i < 100001; i++) {
if (integers[i] == 0) {
lostIntegers.add(i);
}
}
StringBuffer str = new StringBuffer();
for (int i = 0; i < 3; i++) {
str.append(lostIntegers.get(i));
}
String numStr = str.toString();
long newNum = Long.parseLong(numStr);
System.out.println(newNum % 7);
}
}
编辑于 2017-08-24 15:21:59
回复(18)
好多人答案是错的 都没排序 虽然对了 但是测试样例没怼到
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e4 + 5;
int ha[maxn];
int main(){
memset(ha, 0, sizeof(ha));
for(int i = 0; i < 9997; i++){
int x; scanf("%d", &x);
ha[x] = 1;
}
int a[3], cnt = 0;
for(int i = 1; i <= 10000; i++){
if(!ha[i]) a[cnt++] = i;
}
sort(a, a + 3);
string s = "";
for(int i = 0; i < 3; i++)
s = s + to_string(a[i]);
long long ans = atoll(s.c_str()) % 7;
printf("%lld\n", ans);
}
发表于 2018-09-25 12:46:42
回复(1)
#include<stdio.h>
#include<string>
#include<sstream>
using namespace std;
int book[10005];
int main(){
int x,i;
for(i=0;i<9997;i++){
scanf("%d",&x);
book[x]=1;
}
long long sum=0;
string res="",s;
for(i=1;i<=10000;i++)
if(book[i]==0){
stringstream ss;
ss<<i,ss>>s;
res+=s;
}
stringstream ss(res);
ss>>sum;
printf("%d\n",sum%7);
}
发表于 2017-08-31 16:46:41
回复(4)
#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
using namespace std;
int main()
{ int x; bool flag[10003]={false}; for(int i=0;i<10000-3;i++) { cin>>x; flag[x] = true; } long long sum = 0; string s = ""; for(int i=1;i<=10000;i++) { if(flag[i]==false) { stringstream ss; ss<<i; s += ss.str(); } } stringstream ss(s); ss>>sum; cout<<sum%7<<endl; return 0;
}
发表于 2018-01-18 01:47:42
回复(0)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int main(){
const int MAX=10001;
int n,rmn=0,rec[MAX]={0};
vector<int> v;
while(cin>>n){
rec[n]=1;
}
for(int i=1;i<MAX;i++){
if(rec[i]==0){
v.push_back(i);
}
}
sort(v.begin(),v.end());
for(int i=0;i<v.size();i++){
int width=1+log10(v[i]);
int temp=rmn*pow(10,width)+v[i];
rmn=temp%7;
}
cout<<rmn<<endl;
return 0;
}
发表于 2017-08-24 18:58:21
回复(11)
用哈希表记录数字是否出现，将未出现的3个数按升序拼接然后计算除以7的余数即可。
import java.util.Scanner;
public class Main {
static boolean[] appear = new boolean[10001];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
for(int i = 0; i < 9997; i++) appear[sc.nextInt()] = true;
int max = Integer.MIN_VALUE;
String strNum = "";
int count = 0;
for(int i = 1; i <= 10000; i++){
if(!appear[i]){
strNum += String.valueOf(i);
count ++;
if(count == 3) break;
}
}
System.out.println(Long.parseLong(strNum) % 7);
}
}
发表于 2021-02-02 13:22:53
回复(0)
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)
优化的版本：
使用一个长度为10000的数组，数组的下标为连续增长的数字，出现数组值为0，没有出现的数字值为1
遍历这个数组，找出值为0的三个数，此时三个数已经是从小到大排序好了的
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] nums = new int[10000];
for (int i = 1; i <= 9997; i++) {
nums[sc.nextInt() - 1] = 1;
}
StringBuffer buf = new StringBuffer();
for (int i = 0; i < nums.length; i++) {
if (nums[i] = 0) {
buf.append(i + 1);
}
}
long res = Long.parseLong(buf.toString());
System.out.println(res % 7);
}
}
最初版本：
创建一个数组接受出现的所有数字，
对数组遍历，如果当前索引i：a[i]+1!=a[i+1]，说明此时数字不连续，确实的这个数组即为a[i]+1，记录下来便可
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
Sting numString = sc.nextLine();
String[] nums = numString.split(" ");
System.out.println(handle(nums));
}
}
public static int handle(String[] nums) {
int[] missNums = new int[3];
int n = -1;
for (int i = 0; i < nums.length; i++) {
if (Integer.valueOf(nums[i]) + 1 != Integer.valueOf(nums[i + 1])) {
n++;
missNums[n] = Integer.valueOf(nums[i]) + 1;
}
}
Arrays.sort(a);
StringBuffer buf = new StringBuffer();
for (int i = 0; i < missNums.length; i++) {
buf.append(missNums[i]);
}
long result = Long.parseLong(buf.toString());
return result % 7;
}
}
编辑于 2018-08-16 22:46:54
回复(0)
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;
// 划分函数
int Partition(vector<int> &input, int lo, int hi){
int pivotPoint = input[lo];
while(lo < hi){
while((lo < hi) && (input[hi] >= pivotPoint))
hi--;
input[lo] = input[hi];
while((lo < hi) && (input[lo] <= pivotPoint))
lo++;
input[hi] = input[lo];
}
input[lo] = pivotPoint;
return lo;
}
// 快速排序
void Qsort(vector<int> &input, int lo, int hi){
if(lo > hi)
return;
int mi = Partition(input, lo, hi); // 划分出前后两部分
Qsort(input, lo, mi - 1); // 前半部分快速排序
Qsort(input, mi + 1, hi); // 后半部分快速排序
}
int main(int argc, char **argv){
vector<int> input;
vector<int> res;
for(int i = 0; i < 9997; i++){
int num;
cin >> num;
input.push_back(num);
}
Qsort(input, 0, input.size() - 1); // 对输入数组进行快速排序
for(int i = 0; i < 9997 - 1; i++){
if(input[i] + 1 != input[i+1])
res.push_back(input[i] + 1);
}
string snewNum = to_string(res[0]) + to_string(res[1]) + to_string(res[2]);
long long newNum = atoll(snewNum.c_str());
cout << newNum % 7 << endl;
return 0;
}
发表于 2018-08-11 11:33:38
回复(1)
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)
思路：
将数组的元素与自然连续增长的数进行比对。如果不相等那么把该数添加到sb中。
将数组的元素与自然连续增长的数进行比对。如果不相等那么把该数添加到sb中。
import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line;
int index=0;
StringBuilder sb=new StringBuilder();
while((line=br.readLine())!=null){
String[] str= line.trim().split(" ");
for(int i=0;i<str.length;i++){
int c=Integer.parseInt(str[i]);
//e.g.如果缺失1，那么一开始就是2和1比较。不相等，把1添加进来。
if(c!=i+index+1){
sb.append(c-1+"");
index++;
}
if(index==3){
break;
}
}
long klong=Long.valueOf(sb.toString());
System.out.println(klong%7);
}
}
}
发表于 2018-05-10 10:16:57
回复(2)
#include<cstdio>
void qsort(int *arr,int start, int end){
//10000个元素，快速排序了解一下
if(start>=end)return;
int sign=arr[start];
int i=start+1,j=end;
while(i<j){
while(i<end && arr[i]<sign)i++;
while(j>start && arr[j]>sign)j--;
if(i>j)break;
int tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
arr[start]=arr[j];
arr[j]=sign;
qsort(arr,start,j-1);
qsort(arr,i,end);
}
int missedNum(int *arr, int start, int end){
//返回start到end内丢失数字个数
return (arr[end]-end)-(arr[start]-start);
}
int mod7(int front, int back){
int backDigits=0;
int backCopy=back;
while(backCopy!=0){
backCopy/=10;
backDigits++;
}
int backZero=1;
while(backDigits>0){
backZero*=10;
backDigits--;
}
return (front*backZero+back)%7;
}
int main(){
int arr[9997];
for(int i=0;i<9997;i++)scanf("%d",&arr[i]);
//快排
qsort(arr,0,9996);
int miss[3],missed=0;
//找这3个数
for(int i=0;i<9996 && missed<3;i++){
for(int j=0;j<missedNum(arr,i,i+1);j++){
miss[missed]=i+2+missed;
missed++;
}
}
//由于丢的3个数可能很大（最大9998999910000，共13位），因此int存不下，换个思路：
//就例子的10，336，8435来说，把最小的10先模7，得3，把3接到336前面，得到3336，对这个模7，得到4
//把4接到8435前面，48435，模7，就可以得到2
//用mod7函数计算两个数拼接后模7的结果，再嵌套一下
//这种方法需要求模的数最大也就99989999（8位），int足够用
printf("%d\n",mod7(mod7(miss[0],miss[1]),miss[2]));
return 0;
}
不过其实好像本来就不需要排序的一个个对上对不上的就是丢的……orz
#include<cstdio>
int mod7(int front, int back){
int backDigits=0;
int backCopy=back;
while(backCopy!=0){
backCopy/=10;
backDigits++;
}
int backZero=1;
while(backDigits>0){
backZero*=10;
backDigits--;
}
return (front*backZero+back)%7;
}
int main(){
int arr[10001];
int x;
for(int i=0;i<9997;i++){
scanf("%d",&x);
arr[x]=x;
}
int miss[3],missed=0;
for(int i=1;i<=10000 && missed<3;i++){
if(arr[i]!=i){
miss[missed]=i;
missed++;
}
}
printf("%d\n",mod7(mod7(miss[0],miss[1]),miss[2]));
return 0;
}
编辑于 2018-05-03 20:45:35
回复(0)
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;
vals[sc.nextInt()] = 1;
if(vals[i]!=1){
newVal[count]=i;
count++;
}
}
System.out.println(Long.decode(newVal[0]+""+newVal[1]+""+newVal[2])%7);
}
}
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)
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int[] array = new int[10001];
for(int i = 1; i <= 9997; i++)
array[in.nextInt()] = 1;
String sb = new String();
for(int i = 1; i<=10000;i++)
if(array[i] == 0)
sb+=i;
System.out.println(Long.parseLong(sb) % 7);
in.close();
}
}
发表于 2018-03-19 18:45:10
回复(1)
#include<iostream>
#include<set>
#include<string>
#include<cstring>
#include<sstream>
using namespace std;
int main(){
set <int> a;
int x;
for(int i=1;i<=10000;i++){
a.insert(i);
}
for(int i=0;i<9997;i++){
cin>>x;
a.erase(x);
}
set <int>::iterator it;
string s;
stringstream ss;
for(it=a.begin();it!=a.end();it++){
ss<<*it;
s=ss.str();
}
long long m;
ss>>m;
int y;
y=m%7;
cout<<y;
return 0;
}
觉得自己做得挺巧秒的，给定1~10000，那么自己先定义set集合1~10000，然后每次输入都删除对应
元素，剩下的即是遗留的，这道题给我的最大的收获是，我学到了sstream的用法，c++类型转换的
一般法则，很棒，自己做出来的感觉很好。
发表于 2017-11-04 16:55:23
回复(0)
问题信息
难度：
137条回答
37收藏
17311浏览
通过挑战的用户
查看代码-
2022-09-16 09:37:04 -
2022-09-15 23:32:30 -
2022-09-15 21:54:36
-
2022-09-12 21:02:49 -
2022-09-05 15:01:12
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
