首页 > 试题广场 >

找缺失数字

[编程题]找缺失数字

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

给定一个按自然数顺序递增用逗号分割的数组，请找出其中第一个缺失的数。

例如 0 , 1 , 2 , 3 , 4 , 5 , 7 , 8 中，第一个缺失的数是 6。

0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 中，第一个缺失的数是 7。

数据范围： $1 \le n \le 100 \$

输入描述:

给定一个以逗号（,）分割的数字串。

输出描述:

输出缺失的数字

示例1

输入

0,1,2,3,4,5,7

输出

示例2

输入

0,1,2,3,4,5,6,7

输出

算法知识视频讲解

倔强的Chao哥

0到n的和减去输入的n个数的和，不就是缺少的那个嘛

发表于 2019-08-25 19:36:47 回复(4)

Josepy

import java.util.*;
import java.io.*;

public class Main{
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(",");
        for(int i = 0; i < str.length; i++){
            if(i == Integer.parseInt(str[i])){
                i++;
            }else{
                System.out.println(i);
                break;
            }
        }
    }
}

遍历一次即可，遇到缺失的直接退出就好

发表于 2020-04-26 23:23:56 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int s=0,x,k;
    char c;
    bool first=false,flag = false;
    while(cin>>x){
        if(!first){
            k = x;
            first = true;
        }
        if(x!=k && !flag){
            s = k;
            k++;
            flag = true;
        }
        k++;
        cin>>c;
        if(c=='\n')
            break;
    }
    cout<<s<<endl;
    return 0;
}

题目中1,2,3,4,5,7,8的这个用例不符合题意！

发表于 2019-09-11 21:29:40 回复(0)

紫魂的海角

使用二分查找。因为数据本来是连续递增的，因此根据下标就可以计算每个位置原本的数据值。因此可以通过二分搜索找到第一个数字与位置不对应的下标。

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] listStr = sc.next().split(","); //将字符串进行分割
        if(listStr.length == 0) return;
        int low = 0;
        int high = listStr.length-1;
        int flag = Integer.valueOf(listStr[0]); //第一个元素值。因为用例中有1，2，3，4，6，7的例子，第一个元素不是从0开始
        while(low <= high){
            int mid = (low+high)/2;
                 //数字与实际对应，那么前面位置的数字与位置也是对应的，因此向后查找
            if(Integer.valueOf(listStr[mid]) == mid + flag){  
                low = mid+1;
            }else{  //数字与实际不对应，那后面位置的数字也不会对应，向前查找
                high = mid-1;
            }
        }
        System.out.println(low+flag);
    }
}

发表于 2019-07-25 17:47:57 回复(0)

无心2019

#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> a;
    string s;
    cin >> s;
    int cur=0, sign = 1;
    for (int i = 0; i < s.size(); i++)
    {
        if (!isdigit(s[i]))
        {
            a.push_back(cur * sign);
            cur = 0;
            sign = 1;
        }
        else
            cur = cur * 10 + s[i] - '0';
    }
    a.push_back(cur * sign);
    sort(a.begin(),a.end());
    for(int i=1;i<a.size();i++)
    {
        if(a[i]-a[i-1]>1)
        {
            cout<<a[i-1]+1<<endl;
            return 0;
        }
    }
    return 0;
}

发表于 2019-07-16 19:15:58 回复(0)

Python3

TS9527

遍历一次，看到不对的情况输出退出。

class MainActivity:

    def main(self):
        # Read the data
        nums = list(map(int, filter(lambda x: len(x) > 0, input().split(','))))
        if not nums:
            print(0)
            return
        # Traverse
        for ptr, num in enumerate(nums):
            if ptr != num:
                print(ptr)
                return
        print(num + 1)


if __name__ == '__main__':
    M = MainActivity()
    M.main()

发表于 2024-08-24 16:21:16 回复(0)

牛客451356249号

class Solution {

public int missingNumber(int[] nums) {

int start=0;

int end=nums.length-1;

while(true){

if(end-start==1){

return end;

}

int temp=(start+end)/2;

if(nums[temp]>temp){

end=temp;

}else{

start=temp;

}

发表于 2023-05-31 14:04:23 回复(0)

小谷围做题家

package main

import (
    "fmt"
    "strings"
)

func main() {
    var s string
    fmt.Scan(&s)
    arr:=strings.Split(s,",")
    for i:=0;i<len(arr);i++{
        if int(arr[i][0]-'0')!=i{
            fmt.Print(i)
            return
        }
    }
    fmt.Print(len(arr))
}

发表于 2023-03-21 00:53:42 回复(0)

年轻人不要搞窝里斗

nums=list(map(int,input().strip().split(',')))
left=0
n=len(nums)
right=n+1
 
while left<right:
    mid=(left+right)//2
    if nums[mid]==mid:
        left=mid+1
    else:
        right=mid
print(left)

二分法，如果mid往左（包括mid）里没有确实，就应该满足nums[mid]==mid；

所以就可以每次折半啦

发表于 2022-03-03 13:48:16 回复(0)

迟缓的比尔在看牛客

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int buf;
    unsigned long long acc = 0;
    unsigned long long max_n = 0;
        /*输入数据，求和*/
    do{
        cin>>buf;
        if(buf > max_n)
        {
            max_n = buf;
        }
        acc += buf;
    }while(cin.get() != '\n');
    cout<<(1+max_n)*max_n/2-acc<<endl; //计算缺省的数字
    return 0;
}

思路：

每输入一个数，更新最大值，最终可以得到n，然后累计求和，最后做差即可得出结果。

发表于 2021-08-10 20:27:47 回复(0)

炊烟晚霞

题目有说数据是递增的吗？？

发表于 2020-09-03 21:08:51 回复(0)

ccccdz

遍历一遍

import java.util.*;
public class Main {
        public static void main(String args[]){
            Scanner sc=new Scanner(System.in);
            while(sc.hasNext()){
                String[] s=sc.next().split(",");
                for(int i=0;i<s.length-1;i++){
                    if(Integer.parseInt(s[i+1])-Integer.parseInt(s[i])!=1)
                        System.out.println((Integer.parseInt(s[i+1])+Integer.parseInt(s[i]))/2);
                }
            }
        }
}

发表于 2020-08-06 10:45:55 回复(0)

木鱼乳

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] strs = sc.nextLine().split(",");
        int[] nums = new int[strs.length];
        int tmp=0;
        for(int i=0;i<strs.length;i++){
            if(Integer.parseInt(strs[i])!=tmp)break;
            tmp++;
        }
        System.out.println(tmp);
    }
}

发表于 2020-06-29 22:26:56 回复(0)

ADPX丶

异或

import java.util.*;

public class Main{
    
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        
        String[] inputs = input.split(",");
        int[] nums = new int[inputs.length];
        
        for(int i = 0; i < nums.length; i++) 
            nums[i] = Integer.parseInt(inputs[i]);
        
        int ans = solution(nums);
        System.out.println(ans);
    }
    
    private static int solution(int[] nums){
        
        int ans = nums.length;
        for(int i = 0; i < nums.length; i++){
            ans = ans ^ i ^ nums[i];
        }
        return ans;
    }
}

发表于 2020-06-27 14:31:14 回复(0)

金际一线天

#include <iostream>
using namespace std;

int main(int argc, char* argv[]){
    int idx = 1, ans = 0, num;
    char c;
    do{
        cin >> num;
        ans ^= idx;
        ans ^= num;
        idx++;
    }while((c = getchar()) != '\n');
    cout << ans << endl;
    return 0;
}

编辑于 2020-05-25 11:36:03 回复(0)

Java

何止hz

二分搜索问题

import java.util.Scanner;

/**
 * @Author: coderjjp
 * @Date: 2020-05-10 18:55
 * @Description:
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] nums = sc.nextLine().split(",");
//        for (int i = 0; i < nums.length; i++)
//            if (i != Integer.valueOf(nums[i])){
//                System.out.println(i);
//                return;
//            }
        int l = 0, r = nums.length, mid;
        while (l <= r){
            mid = (l + r) >>1;
            if (mid == Integer.valueOf(nums[mid]))
                l = mid + 1;
            else
                r = mid - 1;
        }
        System.out.println(l);
    }
}

发表于 2020-05-10 19:04:54 回复(0)

原反补移码

#include<iostream>
(720)#include<vector>
#include<algorithm>

using namespace std;

int main(void){
    int num;
    char c;
    int n = -1;
    int sum = 0;
    while (scanf("%d%c", &num, &c) && c != '\n'){
        n = max(num, n);
        sum += num;
    }
    int total = n * (n+1);
    cout<<total/2 - sum<<endl;
    return 0;
}

发表于 2020-05-10 15:01:33 回复(0)

Shelven丶

#include<bits/stdc++.h>

using namespace std;

int main(void)
{
	string s, ss;
	cin >> s;
	vector<int> vi;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] != ',')ss += s[i];
		else
		{
			vi.push_back(stoi(ss));
			ss = "";
		}
	}
	vi.push_back(stoi(ss));
	sort(vi.begin(), vi.end());
	for (int i = 0; i < vi.size()-1; i++)if (vi[i] + 1 != vi[i + 1])cout << vi[i] + 1;
}

发表于 2020-04-09 18:37:01 回复(0)

szl201904260905270

#include<iostream>
using namespace std;
int main()
{
    int n,num=0,sum=0;
    while(cin>>n)
    {
        num++;
        sum+=n;
    }
    //cout<<(num+1)*num/2-sum<<endl;
    cout<<'6'<<endl;
    return 0;
}

谁能告诉我发生了什么

发表于 2019-11-10 15:31:19 回复(0)

C/C++

hello古斯卡

//题目说输入是连续的，那就让cur一直加1，再与下一个输入的数比较即可
#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    int n;
    char c;
    cin >> n >> c;
    int cur = n+1;
    while (cin >> n >> c) {
        if (n != cur) {
            cout << cur << endl;
            return 0;
        }
        cur++;
    }

    return 0;
}

发表于 2019-10-06 17:16:49 回复(0)