This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 41 on LeetCode. The first positive number missing is difficult.

Tag: “Bucket sort”

Given an unsorted integer array nums, find the smallest positive integer that does not appear in it.

Advanced: Can you implement a solution with O(n) time complexity and use only constant level extra space?

 

Example 1:

Input: nums = [1,2,0] output: 3Copy the code

Example 2:

Nums = [3,4,-1,1Copy the code

Example 3:

Input: nums = [7,8,9,11,12] output: 1Copy the code

Tip:

  • 0 <= nums.length <= 300
  • –
    2 31 2^{31}     <= nums[i] <=
    2 31 2^{31}     – 1

Bucket sort

If the array length is n, the answer must be in the range [1, n + 1].

So we can use the idea of bucket sort, placing each number where it should appear.

The basic idea is as follows:

  1. Preprocessing is carried out according to bucket sorting idea: ensure that 1 appears innums[0]2 appears in the position ofnums[1]In the position of… .nAppear in thenums[n - 1]Is in the position of. Not in[1, n]The numbers in the range don’t move.

For example, the example [3,4,-1,1] will be preprocessed to [1,-1,3,4].

  1. traversenumsFind the first one that is not where it should be[1, n]The number of. If no data is found, the data is continuous. The answer isn + 1

For example, the first nums[I]! In the preprocessed array [1,-1,3,4]. = I + 1 is the number 2.

Code:

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] >= 1&& nums[i] <= n && nums[i] ! = i +1&& nums[i] ! = nums[nums[i] -1]) {
                swap(nums, i, nums[i] - 1); }}for (int i = 0; i < n; i++) {
            if(nums[i] ! = i +1) return i + 1;
        }
        return n + 1;
    }
    void swap(int[] nums, int a, int b) {
        intc = nums[a]; nums[a] = nums[b]; nums[b] = c; }}Copy the code
  • Time complexity: Each number that should be moved will be moved to the target location at one time. The complexity is O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

Actual combat skills

Remember when I first talked to you in 4. Finding the median of two positive ordinal groups about how we could analyze whether we could do something else to AC for some of the problems that constrained us literally.

This is especially important for games and computer trials where we are required to AC as quickly as possible.

In general, you can judge by the temporal complexity of intuitive solutions, the temporal complexity of textual constraints, and the scope of data.

For this, we can easily think of a way to sort first and iterate again:

The sorting complexity is O(nlog⁡n)O(n\log{n})O(nlogn); The process of finding the answer involves enumerating [1, n] and then “dichotomizing” to find out if the current enumeration value is in the sorted data in order of complexity O(nlog⁡n)O(n\log{n})O(nlogn). So the overall complexity is O(nlog⁡n)O(n\log{n})O(nlogn).

The text requires that we use O(n)O(n)O(n) complexity. At this point we can basically determine that O(nlog⁡n)O(n\log{n})O(nlogn) can do it without looking at the data range.

Because O(nlog⁡n)O(n\log{n})O(nlogn) and O(n)O(n)O(n) O(n)O(n) are not much different, even if the data range is 10710^7107. Log107log {10^7}log107 = 23, the value is very small, O(nlog⁡n)O(n\log{n})O(nlogn) can be equivalent to an O(n)O(n)O(n) O(n)O(n) solution with constant 23. In this case, the data range is only 300, so you can do whatever you want.

O(nlog⁡n)O(n\log{n})O(nlogn)

class Solution {
    public int firstMissingPositive(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 1; i <= n; i++) {
            if (Arrays.binarySearch(nums, i) < 0) return i;
        }
        return n + 1; }}Copy the code

You will find no difference in the execution time between the O(nlog⁡n)O(n\log{n})O(nlogn) and O(n)O(n)O(n) O(n) solutions on LeetCode.

The last

This is the No. 1 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 questions on LeetCode by the start date, some of which have lock questions.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.