首页 > 试题广场 >

数组中未出现的最小正整数

[编程题]数组中未出现的最小正整数

热度指数：2074 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个无序数组arr，找到数组中未出现的最小正整数

例如arr = [-1, 2, 3, 4]。返回1

arr = [1, 2, 3, 4]。返回5

[要求]

时间复杂度为

，空间复杂度为

输入描述:

第一行为一个整数N。表示数组长度。
接下来一行N个整数表示数组内的数

输出描述:

输出一个整数表示答案

示例1

输入

4
-1 2 3 4

输出

示例2

输入

4
1 2 3 4

输出

备注:

算法知识视频讲解

C/C++

nbgao

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

int main(){
    int n;
    cin>>n;
    int a[n], l=0, r=n-1;
    for(int i=0;i<n;i++)
        cin>>a[i];
    while(l<r){
        if(a[l]==l+1)
            l++;
        else if(a[l]<=l || a[l]>r || a[a[l]-1]==a[l])
            a[l] = a[--r];
        else
            swap(a[l], a[a[l]-1]);
    }
    cout<<l+1<<endl;
    return 0;
}

发表于 2020-03-01 00:23:40 回复(0)

无心2019

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int>num(n);
    for(int i=0;i<n;i++)
        cin>>num[i];
    int left=0,right=n-1;
    while(left<right)
    {
        if(num[left]==left+1)
            left++;
        else if(num[left]<=left||num[left]>right||num[num[left]-1]==num[left])
            num[left]=num[--right];
        else
            swap(num[left],num[num[left]-1]);
    }
    cout<<left+1;
    return 0;
}

发表于 2019-08-30 21:39:24 回复(0)

字节快给我oc吧

1. 统计出数组中的正数个数，k个

2. 缺失的正整数或者是k+1，或者在1-k之间

3. 要做的事情就是对于1-k之间的数字，放到它该去的位置，这个过程一定说O(n)内完成的

4. 1-k之间的数都去了它对应的位置，然后遍历，第一个不应该出现的数字就是，如果0-k-1的数字都符合，那就是k+1

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long[] arr = new long[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextLong();
            max += arr[i] > 0 ? 1 : 0;
        }
        for (int i = 0; i < n; i++) {
            long cur = arr[i];
            while (cur > 0 && cur <= max && arr[(int)(cur-1)] != cur) {
                long tmp = arr[i];
                arr[i] = arr[(int)(cur-1)];
                arr[(int)(cur-1)] = tmp;
                cur = arr[i];
            }
        }
        int res = max+1;
        for (int i = 0; i < n; i++) {
            if (arr[i] != i+1) {
                res = i+1;
                break;
            }
        }
        System.out.println(res);
    }
}

发表于 2019-08-21 09:56:36 回复(2)

胖大海201806042211626

def solution(a):
    n = len(a)
    i = 0 
    while i < n: #将a[I]中存储对应的I+1，如果不在[1,n]则进行下一个
        temp = a[i]
        if temp == i+1:
            i += 1
        elif 1<= temp and temp <= n:
            if a[i] == a[temp-1]:
                i += 1
            else:
                a[i] = a[temp-1]
                a[temp-1] = temp
        else:
            i += 1
    res = n + 1
    for i in range(n):
        if a[i] != i+1:
            res = i + 1
            break
    return res
n = input()
a = [int(i) for i in input().split()]
print(solution(a))

最小正整数一定再[1, n+1]中，其中n表示数组长度，将数组的下标和对应位置的数字对应上，遇到第一个不符合的就是未出现的最小正整数。如果全都符合，则为n+1

其中需要注意的是数组中的第一个下标为0，所以a[i]中存储的应该是i+1

发表于 2020-09-21 23:25:59 回复(0)

C/C++

💭💡🎈马豪好厉害

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int a[N];
int main()
{
    int n;
    scanf ("%d",&n);
    for (int i=1;i<=n;i++)
        scanf ("%d",&a[i]);
    for (int i=1;i<=n;i++)
    {
        if (a[i]>=1&&a[i]<=n&&a[i]!=i)
            swap(a[i],a[a[i]]);
     }
    int k=1;
    for (;k<=n;k++)
        if (a[k]!=k) break;
    printf ("%d",k);
   return 0;
}

发表于 2022-12-02 20:07:15 回复(0)

Java

绚都

自己想到的一个方法

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n=Integer.parseInt(sc.nextLine().trim());
            int[] arr=new int[n];
            String[] s = sc.nextLine().trim().split(" ");
            for (int i = 0; i < n; i++) {
                arr[i]=Integer.parseInt(s[i]);
            }
            int res=new Solution().NotOccurred(arr);
            System.out.println(res);
        }
    }
}

class Solution {
    public int NotOccurred(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]>0) swap(arr,arr[i]-1,i);
        }
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]!=i+1) return i+1;
        }
        return arr.length+1;
    }

    public void swap(int[] arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
}

发表于 2022-05-06 16:57:00 回复(0)

C/C++

littlehug

#include <bits/stdc++.h>

using namespace std;

int firstMissingPositive(vector<int>& arr) {
    for (int i = 0; i < arr.size(); ++i) {
        while (!(arr[i] < 1 ||
                 arr[i] > arr.size()-1 ||
                 arr[i] == i+1 || arr[i] == arr[arr[i]-1])) {
            swap(arr[i], arr[arr[i]-1]);
        }
    }

    for (int i = 0; i < arr.size(); ++i) {
        if (arr[i] != i+1) return i+1;
    }
    return arr.size()+1;
}

int main()
{
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    cout << firstMissingPositive(arr);
    return 0;
}

「自然数数组排序」那题先做了会有极大的帮助。此题是自然数数组排序的变形，一边排序、一边筛选不适合的值(负数)或是重複的值，再依序检查遗漏的正整数。

编辑于 2021-03-12 02:42:30 回复(0)

C/C++

codewind

#include<iostream>
using namespace std;
const int N = 1e6+5;
int a[N];
int n;
int main() {
    scanf("%d", &n);
    for(int i=1;i<=n;++i) {
        scanf("%d", a+i);
         
    }
    int l= 1,r = n;
    while(l<r) {
        if(a[l]==l) {
            l++;
        }else if(a[l]<l || a[l]>r  || a[l]==a[a[l]] ) {
            a[l] = a[r--];
        }else {
            swap(a[l],a[a[l]]);
        }
    }
    printf("%d", l);
    return 0;
    
    
    
    
    
    
    
    
    
    
}

发表于 2021-01-31 00:53:19 回复(0)

思考致富

/*
 * @Description: 数组中未出现的最小正整数
 * @Author: 
 * @Date: 2020-11-09 20:30:04
 * @LastEditTime: 2020-11-09 20:59:15
 * @LastEditors: Please set LastEditors
 */
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){

    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i = 0;i < n;i++){//初始的数组
        cin >> arr[i];
    }
    int left = 0;//左边的索引，将数组分为[0,left]和[left+1,right]
    //[0,left]都是满足arr[left] == left + 1
    //[left+1，right]表示待处理部分
    int right = arr.size() - 1;//表示右边界值
    while(left < right){
        //1.表示正常情况
        if(arr[left] == left + 1){
            left++;
        }
        //2.表示出现不合法情况
        //2.1表示在区间[left+1,right]上的数少了一个，因为当前值出现在了[0,left]上
        //2.2表示当前值大于整个区间范围，即不在[0,right]的区间范围
        //2.3表示当前值出现了重复，则[left+1,right]上的数少了一个
        else if (arr[left] <= left || arr[left] > right || arr[ arr[left] - 1 ] == arr[left]){
            right--;//范围缩小，故right需要左移
            arr[left] = arr[right];//将最后位置上的数放在位置left上（这步不是很懂哎……）
        }
        //3.表示当前值是一个合法的值，但是没有在理想的位置上，需要进行交换处理
        else{
            swap(arr[ arr[left] - 1 ], arr[left]);
        }

    }
    cout << left + 1 << endl;
    //system("pause");
    return 0;
}

发表于 2020-11-09 21:01:55 回复(0)

JavaScript

火箭逗地主

while(N=readline()){
let arr=readline().split(' ').map(x=>+x)
arr.sort((a,b)=>a-b)
let i=1
while(i<=parseInt(N)+1){
if(!(arr.includes(i))){
console.log(i)
break;
}
i++
}
}

发表于 2020-07-03 14:05:57 回复(0)

别搁那忽悠人了

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    int arr[n];
    for (int i = 0;i < n;i++){
        cin >> arr[i];
    }
    
    int l = 0;
    int r = n -1;

    while(l < r)
    {
        if(arr[l] == l + 1)//在理想的位置
        {
            l++;
        }
        else if(arr[l] > r || arr[l] <= l || arr[arr[l] - 1] == arr[l])//不合法的数据
        {
            arr[l] = arr[--r];
        }
        else//合法但是没有在理想的位置上
        {
            swap(arr[l], arr[arr[l] - 1]);
        }
 
    }//while
 cout << l + 1 << endl;
    return 0;
}

发表于 2020-05-25 21:01:56 回复(0)

钱多事少离家近

//int a[]= {1,3,4,5};
private static int findnum(int a[]) {	
  int l=0;//l表示已经从1到L已经出现（左边界），l的初值为0。
  int r=a.length;//如果一个数字过大（不合法）扔掉，用r表示这个右边界，r初始值长度
		 while(l<r){
		            if(a[l]==l+1){//a[0]=1,0-k内合法的数有多少
		                l++;
		            }else if(a[l]<=l||a[l]>r||a[l]==a[a[l]-1]){//不合法,
		            	                    //a[1]=3 a[a[1]-1]=a[2]
		                a[l] = a[--r];//缩短右边界
		            }else{//合法但是没有在理想的位置上
		                swap(a,l,a[l]-1);//交换新数l和已排好的a[l]-1
		            }
		        }		       		    		    
	return l+1;//返回a[l]=l+1,0-l为已出现的数，l+1代表未出现的数
}
private static void swap(int[] arr, int a,int b){
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

编辑于 2019-11-21 10:18:55 回复(0)

你好像一个人

左神书上的代码，时间复杂度O(n)，反正我是想不出来的

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int [] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = scanner.nextInt();
        }
        int l = 0;
        int r = n;
        while(l<r){
            if(arr[l]==l+1){
                l++;
            }else if(arr[l]<=l||arr[l]>r||arr[l]==arr[arr[l]-1]){
                arr[l] = arr[--r];
            }else{
                swap(arr,l,arr[l]-1);
            }
        }
        System.out.println(l+1);
    }
    public static void swap(int[] arr, int a,int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

发表于 2019-08-15 14:56:19 回复(0)

提交观点

问题信息

数组双指针

上传者：小小

难度：

13条回答 27收藏 9015浏览

通过挑战的用户

查看代码

asdasdasdb

2023-03-08 21:34:27
zhangco...

2023-02-18 23:03:53
牛客78620...

2022-12-30 19:11:31
星尘OvO

2022-12-16 18:47:01
💭💡🎈马...

2022-12-02 20:13:21

数组中未出现的最小正整数

输入描述:

输出描述:

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题