首页 > 试题广场 >

序列找数

[编程题]序列找数

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

从非负整数序列 0, 1, 2, ..., n中给出包含其中n个数的子序列，请找出未出现在该子序列中的那个数。

输入描述:

输入为n+1个非负整数，用空格分开。
其中：首个数字为非负整数序列的最大值n，后面n个数字为子序列中包含的数字。

输出描述:

输出为1个数字，即未出现在子序列中的那个数。

示例1

输入

3 3 0 1

输出

算法知识视频讲解

无心2019

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,a[100007],i=0,res=0;
    while(cin>>a[i++]);
    n=a[0];
    sort(a,a+n+1);
    if(a[0]!=0)
        res=0;
    for(int i=1;i<n+1;i++)
    {
        if(a[i]-a[i-1]>1)
            res=a[i-1]+1;
    }
    cout<<res<<endl;
    return 0;
}

发表于 2019-06-20 23:11:06 回复(0)

blue.sky

供参考

#include <bits/stdc++.h>
using namespace std;
int main()

	{



	    int nums;



	    scanf("%d", &nums);



	    int* num = new int(nums);



	    for(int i = 0 ; i < nums ; ++i)



	        scanf("%d", &num[i]);



	



	    sort(num, num+nums);



	    int i = 0;



	    for( ; i < nums ; ++i)



	    {



	        if(num[i] != i)



	        break;



	    }



	    cout<<(i)<<endl;



	



	    return 0;



	}

编辑于 2019-04-05 11:38:34 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>

using namespace std;

int main()
{     int n,x;     while(cin>>n)     {         bool a[n+1];         for(int i=0;i<n;i++)         {             cin>>x;             a[x] = true;         }         for(int i=0;i<=n;i++)             if(!a[i])                 cout<<i<<endl;             }     return 0;
}

发表于 2019-01-16 03:36:28 回复(0)

哦哦哦5

有那么麻烦么，输入第一个数n，可以计算得到0-n的总和，输入后面的数统计一个和，作差就是缺的数字

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

int main()
{
    int n;
    cin >> n;
    int sum = n * (n + 1) / 2;
    int sum2 = 0;
    for (int i = 0; i < n; i++)
    {
        int tmp;
        cin >> tmp;
        sum2 += tmp;
    }  
    cout << sum - sum2;
    return 0;
}

发表于 2018-08-22 21:27:39 回复(7)

bettermin

Python3 我居然就这样成功了。。。

def not_have(nums):
    for i in range(len(nums)):
        if i not in nums:
            return i
nums = list(map(int,input().split()))
print(not_have(nums))

发表于 2020-03-26 19:40:10 回复(0)

Java

lmz9509

/*
我有一个比较笨的方法，把这些放到数组里面，然后排序，然后遍历找那两个数之间差值不为1
*/
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader((new InputStreamReader(System.in)));
        String[] str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        int[] arr = new int[n];
        for(int i=0;i<n;i++)
            arr[i] = Integer.parseInt(str[i+1]);
        Arrays.sort(arr);
        for(int i = 0;i<n-1;i++){
            if(arr[i+1] - arr[i] !=1){
                System.out.println(arr[i]+1);
                return;
            }
        }
        System.out.println(0);
    }
}

发表于 2020-06-17 20:46:22 回复(1)

Java

Ys--

//联想到之前有个找只出现一次的数的题，用的异或的思想，不知道有没有缺陷，欢迎指正
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int res = 0;
        for (int i = 0; i < n; i++) {
            res ^= i;
            res ^= s.nextInt();
        }
        System.out.println(res^n);
    }
}

发表于 2019-04-11 16:03:43 回复(0)

C++

池中物_2024

#include <iostream>
using namespace std;

int main() {
    int n, s;
    cin >> n;
    s = n*(n+1)/2;
    while(cin >> n)
        s -= n;
    cout << s;
}

发表于 2022-09-28 16:25:38 回复(0)

Onism_DreamBoat

#include <stdio.h>
int main()
{
    int n,num;
    scanf("%d",&n);
    int array[100]={0};
    int nums[100]={0};
    for(int i=0;i<n;i++){
        scanf("%d",&array[i]);
    }
    for(int i=0;i<n;i++){
        int a=array[i];
        nums[a]=1;
    }
    for(int i=0;i<n;i++){
        if(nums[i]==0){
            num = i;
        }
    }
    printf("%d\n",num);
    return 0;
}

#暴搜法#

发表于 2022-09-15 16:19:18 回复(0)

pein531

遍历计算所有数字的和，以及用高斯求和公式求取在没缺数字情况下的和，两者做差就是缺的数字

data = list(map(int, input().split()))
n = data[0]
arr = data[1:]
print(n*(n + 1)//2 - sum(arr))

发表于 2021-04-09 10:45:44 回复(0)

Python

华科平凡

python

a = list(map(int, input().split()))
for i in range(len(a) + 1):
    if i not in set(a):
        print(i)
        break

发表于 2019-03-16 05:34:07 回复(4)

shijiacheng

/**
 * 序列找数
 * 从非负整数序列 0, 1, 2, ..., n中给出包含其中n个数的子序列，请找出未出现在该子序列中的那个数。
 * 输入描述:
 * 输入为n+1个非负整数，用空格分开。
 * 其中：首个数字为非负整数序列的最大值n，后面n个数字为子序列中包含的数字。
 * 输出描述:
 * 输出为1个数字，即未出现在子序列中的那个数。
 * 输入例子1:
 * 3 3 0 1
 * 输出例子1:
 * 2
 */
public class FindNumberInSequence {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String[] strs = str.split(" ");

        int n = Integer.parseInt(strs[0]);

        if (n > 0) {
            findNoNumber(str.substring(strs[0].length()),n);
        }

    }

    /**
     * 找到未出现在该子序列中的数
     */
    private static void findNoNumber(String s,int n) {
        if (s == null || s.length() == 0)
            return;
        for (int i = 0; i <= n; i++) {
            if (!s.contains(" "+i)) {
                System.out.println(i);
                return;
            }
        }
    }
}

发表于 2018-08-14 23:27:25 回复(0)

liaoming

#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
    int n = 0;
    while (cin >> n) {
        vector<bool> vec(n + 1, false);
        int t = 0;
        while (n--) {
            cin >> t;
            vec[t] = true;
        }
        for (int i = 0; i < vec.size(); ++i) {
            if (!vec[i]) {
                cout << i << endl;
                break;
            }
        }
    }
    return 0;
}

发表于 2018-08-10 08:25:07 回复(0)

Java

松林加油

import java.util.Scanner;

public class Main {
    // 解法: 利用等差数列求和
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long sum = n * (n + 1) >> 1;
        for (int i = 0; i < n; i++)
            sum -= sc.nextInt();

        System.out.println(sum);
    }
}

发表于 2020-08-27 21:37:49 回复(0)

嗯！！！！

s = list(map(int, input().split()))

f = [False for _ in range(len(s))]
re = []
for i in range(len(s)):
    f[s[i]] = True
for i in range(len(s)):
    if not f[i]:
        re.append(i)
if len(re) == 1:
    print(re[0])
else:
    print(' '.join(re))

发表于 2018-08-10 14:33:13 回复(0)

牛客665672417号

#include<stdio.h>
int main(){
    int i,j,n;
    int a[99],b[99];
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=0;i<n;i++)
    {
        b[i]=i;
    }
    for(i=0;i<n;i++)
    {
        for(j=0;j<=n;j++)
        {
            if(a[i]==j)
                b[j]=-1;
        }
    }
    for(i=0;i<n;i++)
    {
        if(b[i]!=-1)
            printf("%d",b[i]);
    }

    return 0;
}

发表于 2022-09-13 19:54:09 回复(0)

Java

马老师的金轮

Scanner scanner = new Scanner(System.in);
//         int max = scanner.nextInt();
//         //输入最大值max
//         int nums[] = new int[max+1];
//         //定义max+1 的数组，当出现一个数nums[i]++ 找出数组下标等于0的数
//         while(scanner.hasNext()){
//             nums[scanner.nextInt()]++;
//         }
//         for(int i=0;i<=max;i++){
//             if(nums[i]==0){
//                 System.out.println(i);
//             }
//         }
        //方法2 把从0到n的数加起来然后在减去输入的数
        int n = scanner.nextInt();
        long sum = n*(n+1)/2;
        while(scanner.hasNext()){
            sum -= scanner.nextInt();
        }
        System.out.println(sum);

发表于 2022-02-17 19:31:15 回复(0)

shangYY


	那么麻烦？直接在输入的字符串中查找是否存在string的contains方法



	   public static void main(String[] args) {



	        Scanner in = new Scanner(System.in);



	        String string = in.nextLine();



	        String[] list = string.split(" ");//只是用到list的长度，即输入数字的个数



	        for (int i = list.length-1; i > -1 ; i--)



	            if (/*字符串i在不在大字符串中*/! string.contains(""+i)) {



	                System.out.println(i);



	                break;



	            }



	    }

发表于 2019-06-12 12:58:30 回复(2)

向宇回桌

import java.util.*;

public class Main {
    private static final int INT_MAX = 0X3f3f3f3f;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        byte[] bits = new byte[n / 8 + 5];
        for (int i=0; i!=n; i++) {
            int num = sc.nextInt();
            bits[num/8] |= (1 << (num % 8));
        }
        for (int i=0; i!=n; i++) {
            if ((bits[i/8] >> (i%8) & 1) != 1) {
                System.out.println(i);
                return;
            }
        }
    }
}

发表于 2019-02-15 22:20:03 回复(0)

C++

青春Java少年不会梦到C艹学姐

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

int n, x, res;
unordered_set<int> st;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++){
        st.insert(i);
    }
    while (n--){
        cin >> x;
        st.erase(x);
    }
    for (auto i : st){
        cout << i;
    }
}

发表于 2025-03-25 14:45:01 回复(0)