Sharing a problem in LeetCode, which is not included in a post, means that the problem is not only a guide to how to solve it, but more importantly, it leads to some tips that can be used elsewhere. Let’s take a look at the description of the problem below.

Problem description

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

Example 1: input: [0] 1 output: 3 example 2: input: [3, 4, 1, 1] output: 2 example 3: input, output,8,9,11,12 [7] : 1Copy the code

Note: Your algorithm should have O(n) time complexity and can only use constant level space.

answer

This problem in leetcode positioning is difficult level, maybe you can try to do it yourself, and then see my solution, below I will analyze step by step, seconds kill big guy please ignore…..

For a problem, if you can’t think of the optimal solution at the first time, I think you can not be so strict, you can first use the method of violence to solve, and then step by step to optimize. Like this, I think, if can you want to use quick sort to sort them first, and then on to solve, it is fairly easy, but high time complexity of O (nlogn), actually we can sacrifice our space complexity under the first, to ensure that our time complexity is O (n), and then slowly to optimize our space complexity.

Method 1: use sets

We know that if the length of the array is n, then the target number we are looking for must be between 1 ~ n + 1, can we put all the number in the array is mapped to a collection, then we can start from 1 ~ n traverse, see which number is not in a set, if not, then this number is the number we are looking for. If 1 to n exists, then the number we’re looking for is n plus 1.

But the thing to notice here is that when we store the numbers in the array, we don’t store them in the set if they’re less than 1 or more than n, because they don’t affect the result, so it’s kind of an optimization. Just talking is not enough, but also need to be able to write code, code as follows:

    public int firstMissingPositive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if(nums[i] >= 1 && nums[i] <= n) { set.add(nums[i]); }}for (int i = 1; i <= n; i++) {
            if(! set.contains(i)) {returni; }}return n + 1;
    }
Copy the code

The bitmap

The space complexity of method one is O(n) in the case of the largest block. I don’t know if you remember bitwise algorithm, but we can use bitwise algorithm to optimize our space. If you don’t know bitwise algorithm, you can read an article I wrote directly:

1. What is bitmap algorithm?

2. Implement bitmap algorithm by code;

By using the bitwise algorithm, we can reduce the space complexity by 8 times, from O(n) -> O(n/32), but O(n/32) is still O(n), but in practice, it does make us run faster. In Java, there are already classes that support bitwise algorithm. BitSet, which I’m sure you’ll understand if you haven’t studied it, looks like this:

    public int firstMissingPositive2(int[] nums) {
        BitSet bitSet = new BitSet();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if(nums[i] >= 1 && nums[i] <= n) { bitSet.set(nums[i]); }}for (int i = 1; i <= n; i++) {
            if(! bitSet.get(i)) {returni; }}return n + 1;
    }
Copy the code

Method 3: Final version

If this array were ordered, that would be fine, but if we wanted to sort it, and we needed order nlogn time, is there a way we could sort it, and not have that high time?

The answer is yes, just now we said, for those numbers less than 1 or greater than n, we can actually ignore, even we, we need to deal with these numbers, they are between 1 and n, then you have to sort these numbers between 1 and n, and we can also ignore the repeated elements. Just record one, so can you sort it in order n time?

I don’t know if you remember the subscript that I wrote?

Summary of some commonly used algorithm techniques.

Or do you remember counting sort? (Counting sort is actually an application of subscripts.)

If you’ve learned counting sort, you probably know that counting sort requires us to open a new array, but we don’t need that. We can do this: For example, nums[I] can be placed at nums[I] -1, so that all numbers 1<=nums[I]<=n are in a relatively ordered position. Notice, I’m talking about relative, which means that for numbers like 1 minus n, anything less than 1 or greater than n we don’t care about. For example, for this array nums[] = {4, 1, -1, 3, 7}.

Nums [I] = nums[i-1], and nums[I]<=0 or nums > n can be ignored, so the process is as follows: start at 0 and iterate to the right

1. Place 4 at the position with subscript 3. In order not to lose the number with subscript 3, swap the number with 4.

2. At this point we can’t move to the right of the number with index 1, because our current 3 is not in order yet and we have to keep working on it, so we switch 3 with index 2

3, the current position is -1, ignore it, advance to the position with the subscript 1, swap 1 with the subscript 0

4, the current position is -1, ignore it, advance to the position of the subscript 2, now 3 is in the orderly position, ignore it and continue to move forward, 4 is also in the orderly position, continue to move forward.

When 7 > n, ignore it and move on.

When we’re done, the numbers between 1 and n are in order, and for those less than 1 or greater than n, we ignore it and pretend not to see it.

Note that nums[I] and nums[I]-1 do not swap if they are equal.

Next, we iterate through the array again from indices 0 to n-1, and if we encounter nums[I]! = I + 1, and then we have our target number, which is I + 1.

Ok, I think I said a little wordy, but also step by step to show you the topic process, even I feel a little wordy, big guy don’t spray ha. The final code is as follows:

    public int firstMissingPositive(int[] nums) {
        if(nums == null || nums.length < 1)
            return 1;
        int n = nums.length;
        for(int i = 0; i < n; I ++){// If nums[I] is equal to nums[I]-1, we don't swap nums[I].while(nums[i] >= 1 && nums[i] <= n && nums[i] ! = i + 1 && nums[i] ! = nums[I]-1){// Swap with nums[I]-1 int TMP = nums[I]; nums[i] = nums[tmp - 1]; nums[tmp - 1] = tmp; }}for(int i = 0; i < n; i++){
            if(nums[i] ! = i + 1){returni + 1; }}return n + 1;
    }
Copy the code

This problem I think is worth learning a lot of places, such as it through the method of place swap, make the specified range of arrays ordered.

There is this method of solving the problem by array subscript is also a common technique, for example, give you a deck of cards, let you shuffle the order, and then distribute to four people, can also use this method, see the problem: what is the shuffling algorithm.

Finally, to promote my public number: helpless and painful code farmers: the public number has more than 100 original documents, but also to share a lot of practical tools, massive video resources, e-book resources, attention from the self. Click scan code to follow oh. Poke me and pay attention,