程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [LeetCode][Java] First Missing Positive

[LeetCode][Java] First Missing Positive

編輯:C++入門知識

[LeetCode][Java] First Missing Positive


題目:

 

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.


題意:

給定一個未排序的整數數組,找出第一個錯過的正整數。

比如:

給定[1,2,0] 返回3,

[3,4,-1,1]返回2.

算法要求O(n) 時間復雜度和常數空間。

算法分析:

最簡單的思路就是對數組進行快速排序,但是由於要求O(n) 的時間復雜度,所以快速排序顯然是行不通的。

 

因此為了搜尋元素,這裡采用數組的下標作為其索引,即對數組的元素進行交換,將正數i放到i-1的位置上,對於負數和大於數組長度的元素棄之不顧。這樣線性掃描一下數組就能得到第一個不存在的正數,即第j位置的元素不等於j+1

 

AC代碼:

 

public class Solution 
{
    public int firstMissingPositive(int[] A) 
    {
        //將正數放到值-1的位置上,這樣1放在0號位置,2放在1號位置,。。。。
        if(A==null || A.length==0)
            return 1;
        for(int i=0;i0 && A[A[i]-1]!=A[i])//這裡A[A[i]-1]!=A[i]這個限制條件的意思是,已經滿足條件的就不交換了
            {
                int temp=A[A[i]-1];
                A[A[i]-1]=A[i];
                A[i]=temp;
                i--;
            }
        }

        for(int i=0;i

 

 

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved