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

LeetCode 41:First Missing Positive

編輯:C++入門知識

LeetCode 41: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.

 

 //類似於桶排序,交換數組元素,使得數組中第i位存放數值(i+1);
 //最後遍歷數組,尋找第一個不符合此要求的元素,返回其下標。整個過程需要遍歷兩次數組,復雜度為O(n)。
 class Solution {
 public:
	 int firstMissingPositive(vector& nums) {
		 int n = nums.size();
		 for (int i = 0; i < n; ++i)
		 {
			 while (nums[i]>0 && nums[i] < n && nums[nums[i]-1] !=nums[i])
				 swap(nums[nums[i]-1], nums[i]);
		 }
		 for (int i= 0; i < n; ++i)
		 {
			 if (nums[i] != i + 1)
				 return i + 1;
		 }
		 return n + 1;
	 }
 };

\

 

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