41. First Missing Positive

2017-03-23  本文已影响175人  codingXue

问题描述

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.

问题分析

这是一道hard题,自己没有思路TAT,在网上搜了解答

分析题意

做法

  1. 第一次遍历数组,若nums[i]的值在1,n之间且nums[nums[i]-1] != nums[i],则交换nums[nums[i]-1]和nums[i]。nums[nums[i]-1] != nums[i]包含两层含义,1)如果nums[i] != i+1,则nums[i]-1 != i,那么nums[i]需要被调换到它应该去的位置;如果nums[nums[i]-1] == nums[i]说明待交换的两个数字相等,则不需交换,否则会死循环。需要注意的是,如果被换到nums[i]位置的数字依然符合交换条件,那么需要继续进行交换,也就是说这里不是一个if判断,而是一个while循环。
  2. 第二次遍历数组,找到第一个nums[i] != i+1的位置,返回i+1。

复杂度分析
虽然这个思想还是蛮好理解,但是在一个for循环里又出现了一个while循环,它的复杂度能是O(n)吗?其实是酱紫,算法复杂度应该看的是基本操作的次数,在这个问题里,基本操作指的是交换操作,而每次交换操作,都至少有一个数字去了它应该去的地方,那么一个n长度的数组,最多只需要n次交换操作,所以它的复杂度是O(n)的~

AC代码

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

Runtime: 3 ms, which beats 70.66% of cpp submissions.

上一篇下一篇

猜你喜欢

热点阅读