首页 > 试题广场 >

找缺失数字

[编程题]找缺失数字
  • 热度指数:2491 时间限制: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

输入

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

输出

6
示例2

输入

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

输出

8
0到n的和减去输入的n个数的和,不就是缺少的那个嘛
发表于 2019-08-25 19:36:47 回复(4)
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)
#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)
#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)
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)
遍历一遍
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)
异或
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)
二分搜索问题
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)
#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)
#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)
//题目说输入是连续的,那就让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)
import java.util.Scanner;
import java.util.Arrays;
public class Main{
    public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            String line = sc.nextLine();
            String[] split = line.split(",");
            int len = split.length;
            int[] arr = new int[len];
            for(int i=0;i<len;i++) {
                arr[i]=Integer.valueOf(split[i]);
            }
            Arrays.sort(arr);//排序
            int start = arr[0];//这道题,第一个数一定对,用例有问题。。。
            for(int i=1;i<len;i++) {
                start++;
                if(arr[i]!=start) {
                    System.out.println(i+arr[0]);
                    break;
                }
            }
        }
}
发表于 2019-09-13 22:38:40 回复(0)