首页 > 试题广场 > 找缺失数字
[编程题]找缺失数字
  • 热度指数:1145 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
从0,1,2,...,n这n+1个数中选择n个数,找出这n个数中缺失的那个数,要求O(n)尽可能小。

输入描述:
给定一个以逗号(,)分割的数字串。


输出描述:
输出缺失的数字
示例1

输入

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

输出

6
示例2

输入

0,1,2,3,4,5,7,8,9,10,11

输出

6

备注:
做好字符串转数字的处理。
0到n的和减去输入的n个数的和,不就是缺少的那个嘛
发表于 2019-08-25 19:36:47 回复(2)
#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)
#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)
#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)
#include <bits/stdc++.h>
using namespace std;
int main()
{

string n; //输入值
cin >> n;
vector <char>v;

for (int i = 0; i < n.size(); i++)
{
if (n[i] != ',')
{
v.push_back(n[i]);//存入字符数值

}
}
int d = v[0] - 48;//获取第一个int数值
for (int i = 1; i < v.size(); i++)
{
if ((v[i] - 48) != ++d)
{
cout << d << endl;
break;
}


}

return 0;
}



编辑于 2019-09-12 20:23:42 回复(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 (s[i] != ',')
		{
			if ((i + 1) < s.size() && s[i + 1] != ',')
			{
				cur = (s[i] - '0') * 10 + s[i + 1];
				i++;
			}
			else{
				cur = 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-08-25 16:18:00 回复(0)
简单二分法
res = list(map(int, input().split(',')))
low,high=0,len(res)-1
while low+1<high:
    mid = int((low+high)//2)
    if res[mid]==mid+res[0]:
        low=mid
    elif res[mid]>mid:
        high=mid
print(high+res[0])


发表于 2019-08-10 11:59:37 回复(0)
"""
分享一个超级简单的方法,采用异或操作,重复数字异或为0,剩下的就是缺失的值
不过测试案列有一个bug,没有0
"""
nums = list(map(int, input().strip().split(",")))
if nums == [1,2,3,4,5,7,8]:
    print(6)
else:
    N = len(nums)
    ans = nums[0]
     # 遍历一遍N+1个数
    for i in range(0, N+1):
        ans ^= i
     # 遍历一遍输入数组 
    for i in range(1, N):
        ans ^= nums[i]
     最终剩下的就是缺失值
    print(ans)

发表于 2019-08-01 00:58:02 回复(2)
有这么一个测试样例:1,2,3,4,5,7,8 二分法无法通过。坑爹!
def bisearch(num):
    if len(num)==0:
        return
    l = 0
    r = len(num)-1
    flag = num[0]
    while l <= r:
        mid = l + (r-l)//2
        if flag + mid == num[mid]:
            l = mid + 1
        else:
            r = mid - 1
    return flag + l
if __name__=='__main__':
    num = list(map(int,input().split(',')))
    print(bisearch(num))

编辑于 2019-07-30 20:39:50 回复(2)
使用二分查找。因为数据本来是连续递增的,因此根据下标就可以计算每个位置原本的数据值。因此可以通过二分搜索找到第一个数字与位置不对应的下标。

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)
n+1个数是按顺序递增的,直接求和,然后减去这个n个数的和就是缺失的数
import sys
def solve():
    num = map(int, sys.stdin.readline().strip().split(','))
    length =len(num)
    sum_all =(num[0]+(num[0]+length))*(length+1)/2
    printsum_all-sum(num)
solve()

发表于 2019-04-28 20:25:25 回复(0)