參考博客?https://www.cnblogs.com/apeway/p/10764597.html?

?

題目描述

給定一個無序數(shù)組arr，找到數(shù)組中未出現(xiàn)的最小正整數(shù)

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

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

?

[要求]

時間復雜度為O(n)O(n)，空間復雜度為O(1)O(1)

?

示例1

輸入

[-1,2,3,4]

返回值

1

?

先看一個時空復雜度均為O(n)的方案，思路如下：

???????? 新建一個和原數(shù)組大小一致的新數(shù)組，通過遍歷原數(shù)組將其中每個元素e(忽略掉小于1或大于數(shù)組長度的元素)填充到新數(shù)組中[e-1]位置上。之后遍歷新數(shù)組就可找到目標，這個遍歷可能會遇到兩種情況，一般情況下，上一步的操作總有被忽略的元素，每忽略一個數(shù)，新數(shù)組中就會少填充一個正整數(shù)，如{-1,1,2,5,6}>>{1,2,0,0,5}，這種情況要找的數(shù)就是第一個值為0的元素的下標+1；極端情況下，上一步的操作沒有被忽略的元素，如{3,2,1,5,4}>>{1,2,3,4,5}，這種情況要找的數(shù)就是length+1； ???????? 為什么開辟的新數(shù)組大小要和原數(shù)組大小一致？這是為了確保在極端情況下能夠容納下由原數(shù)組中元素組成的從1開始的最長連續(xù)整數(shù)序列。 ???????? 為什么要忽略掉大于數(shù)組長度的元素？這是因為如果存在這樣的數(shù)X，剩下的小于length個元素不可能組成1~length的連續(xù)整數(shù)序列，則X更不可能在連續(xù)序列中，就沒必要維護它了。

?將空間復雜度均為O(n)改進成O(1)如下:

package datastructure;import java.util.Arrays;public class MinNumberdisappered {public static void main(String[] args) {//int[] arr = {-1, 2, 3, 4};int[] arr = {1, 2, 3, 4};MinNumberdisappered minNumberdisappered = new MinNumberdisappered();int ret = minNumberdisappered.minNumberdisappered(arr);System.out.println(ret);}/*** return the min number* @param arr int整型一維數(shù)組 the array* @return int整型*/public int minNumberdisappered (int[] arr) {System.out.println("原數(shù)組:" + Arrays.toString(arr));/** right是一個邊界值，表示用數(shù)組中元素組成的從1開始的連續(xù)整數(shù)序列中可能的最大值（初始等于數(shù)組長度）。* 處理數(shù)組過程中如果遇到比right大的數(shù)，就表示該數(shù)不合法，應該被丟掉（代碼中還處理了其它表示數(shù)不合法的情況）。* >> 隨著數(shù)組元素被處理，每遇到一個不合法的元素，就應將right減1。*/int right = arr.length;/** 索引left（初始為0），left將數(shù)組分成兩部分。* [0,left)是處理完成的部分，其中每個元素都滿足a[i]=i+1;* [left,right]是待處理部分。* >> 隨著數(shù)組元素被處理，left會逐漸向右移動。*/int left = 0;while (left + 1 <= right) { // 正在處理的元素的值(left+1) <= 邊界值// 分支1、arr[left]在理想的位置// 則處理完成部分長度加1，然后繼續(xù)處理未完成部分的下一個待處理元素if (arr[left] == left + 1) {left++;}// 分支2、arr[left]是不合法的數(shù)據(jù)// 則先將right減1，然后丟掉不合法的數(shù)并將待處理部分最后一個元素填充到left位置繼續(xù)處理else if (arr[left] < left + 1 || arr[left] > right) {right--;arr[left] = arr[right];}// 分支3、arr[left]合法，但是沒有在理想的位置上// 則需要交換arr[left]與其理想位置上元素，然后繼續(xù)處理交換后left位置處的元素// 求理想位置p的索引：p+1 = arr[left] >> p = arr[left]-1else {// 如果要交換的兩個元素相同，也算當前處理的元素arr[left]不合法，進行與分支2一樣的處理if(arr[left] == arr[arr[left] - 1]) {right--;arr[left] = arr[right];} else {swap(arr, left, arr[left] - 1);}}}System.out.println("處理后:" + Arrays.toString(arr));return left + 1;}private void swap(int[] a, int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;} }

?

總結(jié)

以上是生活随笔為你收集整理的常考数据结构与算法:数组中未出现的最小正整数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。