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

#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;
}

#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;
}

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))

#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;
}

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;
    }
}

#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;
}

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

#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;
    
    
    
    
    
    
    
    
    
    
}

/*
 * @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;
}

#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;
}

//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;
}