首页 > 试题广场 >

找缺失数字

[编程题]找缺失数字
  • 热度指数:2494 时间限制: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
二分搜索问题
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)
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)

问题信息

上传者:小小
难度:
2条回答 5009浏览

热门推荐

通过挑战的用户

查看代码