Reference to missing numbers in Offer 53-II. 0 to n-1

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

1, the title

All numbers in an incrementally sorted array of length n-1 are unique, and each number is in the range 0 to n-1. Find one and only one of the n digits in the range 0 to n-1 that is not in the array.

Example 1:

Input: [0, 1, 3]

Output: 2

Example 2:

Input: [0, 1, 2, 3, 4, 5, 6, 7, 9]

Output: 8

Tip:

  • 1 <= Array length <= 1000

2, train of thought

Method one: binary search

  1. Based on the idea of dichotomy, find the middle position first
  2. nums[M] == MIndicates that the subscript of the current element is equal to itself. For example, [0, 1, 2, 3, 4, 5] the subscript of each element is equal to the value of the element[start,mid]The interval is not missing any numbers
  3. So we can be sure that what’s missing is[mid+1,end]In the interval

Method two: sum

Let’s first generalize the formula for summation of arithmetic sequences

  • The NTH term is equal to the first term plus the number of terms minus 1 times the toleranceThe last entry of an array of length is(length - 1) * 1
  • sumSn = [ n * (a1 + an)] / 2So the arithmetic sequence is summationSn = length * (0 + length - 1) / 2
  1. If the array is not short of numbers, all the numbers in the array can form an arithmetic sequence
  2. Just sum up the formula and subtract all the numbers in the array to figure out which number is missing.
  3. We can see that they gave us one less array so the sum formula for this is going to change to 1Sn = (length + 1) * (0 + length) / 2

Method three: violent solution

They say it’s an incrementally sorted array, so you just go back and forth, and you return whatever’s missing

3, code,

Commit AC for the first time

class Solution {
    public int missingNumber(int[] nums) {
        int L = 0;
        int R = nums.length - 1;
        while(L <= R){
            int M = (L + R) >> 1;
            if(nums[M] == M) L = M + 1;
            else R = M - 1;
        }
        returnL; }}Copy the code

Time complexity: O(logn) Space complexity: O(1)

Commit the SECOND TIME

class Solution {
    public int missingNumber(int[] nums) {
        int length = nums.length;
        int sum = (length + 1) * (0 + length) / 2;
        for (int i = 0; i < length; i++)
            sum -= nums[i];
        returnsum; }}Copy the code
  • Time complexity: O(n)
  • Space complexity: O(1)

Commit AC for the third time

class Solution { 
    public int missingNumber(int[] nums) {
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            if(nums[i] ! = i)return i;
        }
        returnlength; }}Copy the code
  • Time complexity: O(n)
  • Space complexity: O(1)

4, summarize

The topic of the use of binary search application example, first of all to understand the binary method.

Dichotomy template:

public static int binarysearch(int arr[], int L, int R, int target){
    int count = 0;
    int M = (L + R) >> 1;
    if(L > R) return -1;

    if (target > arr[M]){
        return binarysearch(arr, M + 1, R, target);
    }else if(target < arr[M]){
        return binarysearch(arr, L, M - 1, target);
    }else {
        returnM; }}Copy the code

❤️ from the LeetCode Basic Algorithms column subscribe to ❤️

The original intention of the director to write blog is very simple, I hope everyone in the process of learning less detours, learn more things, to their own help to leave your praise 👍 or pay attention to ➕ are the biggest support for me, your attention and praise to the director every day more power.

If you don’t understand one part of the article, you can reply to me in the comment section. Let’s discuss, learn and progress together!

Offer 53-II. 0 ~ n-1