首页 > 试题广场 >

序列找数

[编程题]序列找数

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

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

输入描述:

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

输出描述:

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

示例1

输入

3 3 0 1

输出

算法知识视频讲解

Java

xiaoL9

Java，将出现的数字值作为数字的下标，并设置为1，然后遍历数组，找到没有出现过的值，也就是nums[i]==0的下标值。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n+1];
        //将出现的数字值作为数字的下标，并设置为1
        while(in.hasNextInt()) {
            nums[in.nextInt()] = 1;
        }
        //找到没有出现过的值，也就是nums[i]==0
        for(int i=0; i<nums.length; i++) {
            if(nums[i] == 0) {
                System.out.println(i);
            }
        }
    }
}

发表于 2023-07-26 10:01:42 回复(0)

Java

勇敢羊羊，不怕困难

import java.util.*;

public class Main{
public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        String[] str = s.nextLine().split(" ");
        int[] arr = new int[str.length];

        for(int i = 1;i<str.length;i++){
            int temp=Integer.parseInt(str[i]);
            arr[temp]++;
        }
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]==0){
                System.out.println(i);
            }
        }
    }     
}

开辟一个新String数组，把输入的列子用空格切分放进String数组。然后把String数组的元素从index=1作为arr的脚标对arr进行操作。arr里str中有的脚本，进行加一。被漏掉的数就是arr中为值0的元素的角标

发表于 2022-08-11 16:22:32 回复(0)

Java

-Jetaime

import java.io.*;

public class Main{
public static void main(String[] args) throws Exception{
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken();
int n = (int)st.nval;
int res = 0;
for(int i = 0; i < n; i++){
st.nextToken();
res = res ^ i ^ (int)st.nval;
}
System.out.println(res ^ n);
}
}

发表于 2022-05-16 17:50:12 回复(0)

Java

tiaodo

import java.util.*;
public class Main{
public static void main(String love[]){

Scanner in=new Scanner(System.in);
int n=in.nextInt();
ArrayList arrays= new ArrayList();

for(int i=0;i<n;i++){
int a= in.nextInt();
arrays.add(a);

}
for(int i=0;i<n;i++) {
if (arrays.contains(i)) {

} else {
System.out.print(i);
break;
}
}
}}

发表于 2022-05-14 12:11:32 回复(0)

Java

布丁布灵

这一题我想复杂了，最简单的方法就是利用等差数列的和减去输入元素的和
记录一下快速排序的解法，利用快速排序中每一次partition会将一个数放置到有序的位置上，本题排序后，数组还满足以下条件

缺失数之前的数满足:i==nums[i]，即索引等于值

缺失数之后的数满足:i==nums[i]+1

import java.util.*;
public class Main {
  static int res = 0;
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int[] nums = new int[n];
      for (int i = 0; i < n; i++) {
          nums[i] = sc.nextInt();
      }
      //利用快排每次确定一个数的位置的特性来找
      quickSort(nums, 0, n - 1);
      System.out.println(res);

  }
  static void quickSort(int[] nums, int l, int r) {
      //这里不能写成l>=,虽说在快排中，单个元素不需要进行排序
      //但是这里是要找到缺失的值，所以每个元素都应该被partition遍历过
      if (l > r)return;
      int p = partition(nums, l, r);
      //System.out.println(p+"->"+nums[p]);
      if(p==nums[p]){
          quickSort(nums, p + 1, r);
      }
      else{
          res=p;
          quickSort(nums, l, p - 1);
      }

  }
  static int partition(int[] nums, int l, int r) {
      int i = l + 1;
      int j = r;
      while (i <= j) {
          while (nums[i] <= nums[l] && i < r)i++;
          while (nums[j] > nums[l] && j > l)j--;
          if (i >= j) {
              break;
          }
          int tmp = nums[i];
          nums[i] = nums[j];
          nums[j] = tmp;

      }
      int tmp = nums[l];
      nums[l] = nums[j];
      nums[j] = tmp;
      return j;
  }
}

发表于 2022-04-28 14:03:58 回复(0)

Java

牛客330565546号

import java.util.*;


public class Main {

        public static void main(String[] args){
            Scanner s = new Scanner(System.in);
            String line_num = s.nextLine();
            String[] s1 = line_num.split(" ");
            int n = Integer.parseInt(s1[0]);
            int count = 0;
            Set set = new LinkedHashSet<Integer>();
            for(int i=1;i<s1.length;i++){
                int anInt = Integer.parseInt(s1[i]);
                set.add(anInt);
            }
           for(int i=0;i<n;i++){
               if (set.contains(i)) {
                   continue;
               }else{
                   System.out.println(i);
               }
           }

        }

}

发表于 2022-04-02 13:09:32 回复(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)

Java

nobrong

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] str = br.readLine().split(" ");
int[] ints = new int[str.length];
for (int i = 0; i < ints.length; i++) {
ints[i]=-1;
}
for (int i = 0; i < str.length; i++) {
int s = Integer.parseInt(str[i]);
ints[s] = s;
}
for (int i = 0; i < ints.length; i++) {
if (ints[i]==-1){
System.out.println(i);
}
}
}
}

发表于 2021-05-17 11:20:13 回复(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)

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)