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

leetcode筆記:First Missing Positive

編輯:C++入門知識

leetcode筆記: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[3, 4, -1, 1]第一個未出現的正整數是2,則返回2。算法要求在O(n)的時間復雜度及常數空間復雜度內完成。

一種方法是,先把數組裡每個正整數從i位放到第i-1位上,這樣就形成了有序的序列,然後檢查每一下標index與當前元素值,就能知道當前下標所對應的正整數是否缺失,若缺失則返回下標index + 1即可。

三. 示例代碼

#include 
#include 

using namespace std;

class Solution
{
public:
    int firstMissingPositive(vector& nums)
    {
        int n = nums.size();
        for (int i = 0; i < n; ++i)
        {
            int temp = 0;
            while (i + 1 != nums[i] && nums[i] != nums[nums[i] - 1] && nums[i] > 0)
            {
                temp = nums[i];
                nums[i] = nums[temp - 1];
                nums[temp - 1] = temp;
            }
        }

        for (int i = 0; i < n; ++i)
        {
            if (i + 1 != nums[i])
                return i + 1;
        }

        return n + 1;
    }
};

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