首页 > 试题广场 > 找缺失数字
[编程题]找缺失数字
从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

备注:
做好字符串转数字的处理。
#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)
简单二分法
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 回复(1)
有这么一个测试样例: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)