java, beat 95%, O(1) space solution


  • 1
    H

    very simple solution. The procedure is as following:

    1. scan through the array
    2. if the number should be at a position in front of the current position (smaller than the current index), swap the number to the correction position; if the new number at the current position is still smaller than the current index, keep on swapping
    3. Now the array should be [1, 2, 3, ...] until the first missing positive number, find this number.

    I've tested many cases, the numbers of swaps are always smaller than the length of the array. Any one help me to prove that this algorithm is O(n) time.

    public class Solution {
        public int firstMissingPositive(int[] nums) {
            int n = nums.length;
            for (int i = 0; i < n; i++){
                int num = nums[i];
                while (num - 1 < i && num > 0 && nums[i] != nums[num -1]){
                    // swap(nums, num - 1, i);
                    nums[i] = nums[num - 1]
                    nums[num - 1] = num;
    
                    num = nums[i];
                    // print(i, nums);
                }
            }
            for (int i = 0; i < n; i++){
                if (nums[i] != i + 1)
                    return i + 1;
            }
            return n + 1;
        }
    
    }

  • 0
    M

    The run-time complexity of the algorithm depends upon the number of swaps required on the input. There are 2 critical observations here:

    1. A swap ensures that at least one of the two elements involved in the swap (at least the element that initiates the swap - index i element) is at its rightful position, and
    2. Once a number is at its rightful position/index, it's never swapped again.

    Therefore, given that there are n elements, and every swap ensures that at least 1 elements is never swapped again, there are at most n swaps required.

    Thus, the first loop in your code runs in O(n) time. The second loop is a simple traversal and also runs in O(n) time. Thus, total runtime of algorithm is O(n).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.