This is the 14th day of my participation in Gwen Challenge

Peak Index of mountain Array (852)

Topic describes

Arr. Length >= 3 There exists I (0 < I < arr. Length – 1) such that: ARr [0] < arr[1] <… arr[i-1] < arr[i] arr[i] > arr[i+1] > … > arr[arr.length-1] gives you the range array arr of integers, returning anything that satisfies arr[0] < arr[1] <… arr[i – 1] < arr[i] > arr[i + 1] > … > arr[arr.length-1] subscript I.

Example 1:

Input: arr = [0,1,0] output: 1Copy the code

Example 2:

Input: arr = [0,2,1,0Copy the code

Example 3:

Arr = [0,10,5,2] output: 1Copy the code

Example 4:

Input: arr = [3,4,5,1Copy the code

prompt

  • 3 <= arr.length <= 104
  • 0 <= arr[i] <= 106
  • Subject data guaranteearrIt’s an array of mountains

** Advanced: ** It is easy to think of time complexity O(n) solutions, can you design an O(log(n)) solution?

Thought analysis

The O(n) solution is really easy to get along with. For this kind of mountain problem, we can also use dichotomy. The problem says that there is only one peak, so the problem is relatively simple, can be divided into uphill and downhill, the highest point is higher than the left point and the right point. We divide the situation into two types, uphill and downhill, and judge.

This problem can not use the usual dichotomy routine, because the situation is very simple, can be directly divided into two cases.

The code shown

Solution 1: Time complexity is O(logn){O(logn)}O(logn), space complexity is O(1){O(1)}O(1).

public int peakIndexInMountainArray(int[] arr) { / /,10,5,4,3,2,1 [0]
        int low = 0;
        int high = arr.length - 1;  / / > = 3

        while (low <= high){
            int mid = low + (high - low)/2;  //arr[4] = 2
            if (arr[mid] > arr[mid - 1]) {/ / up hill
                if (arr[mid] > arr[mid + 1]) {return mid;
                }
                // mid < mid + 1 //
                low = mid + 1;

            } else {  / / downhill
                if (arr[mid - 1] > arr[mid - 2]) {return mid - 1;
                }
                high = mid - 1; }}return -1;

    }
Copy the code

Looking for peaks (162)

Topic describes

Peak elements are those whose values are greater than their left and right neighbors.

Given an input array nums, find the peak element and return its index. The array may contain multiple peaks, in which case you simply return the location of any one of the peaks.

You can assume that NUMs [-1] = nums[n] = -∞.

Advanced:

  • You can be inO(n log n)In time complexity?

Example 1:

Input: nums = [1,2,3,1] output: 2 explanation: 3 is the peak element, and your function should return its index 2.Copy the code

Example 2:

Input: nums = [1,2,1,3,5,6,4] Or return index 5 with a peak element of 6.Copy the code

prompt

  • 1 <= nums.length <= 1000
  • -231 <= nums[i] <= 231 – 1
  • There is nums[I] for all valid I! = nums[i + 1]

Thought analysis

We can assume that nums[-1] = nums[n] = -∞, which means that the left and right sides are infinitesimals. This is also important for determining the peak value. This is the same type of problem as the one above, but since there are multiple peaks, we only need to pull out one peak, so there are more boundary conditions to deal with.

Binary search has certain routines, first define low and high. The judgment condition of the while loop is always low <= high. For low == high, special processing is made when necessary, and the return value is always mid. Low = mid + 1 and high = mid – 1;

For the non-deterministic search, the pre – and post-detection method is used to determine the search interval. We deal with hits first, and then we deal with left and right half look-ups.

The code shown

Solution 1: Time complexity is O(logn){O(logn)}O(logn), space complexity is O(1){O(1)}O(1).

public int findPeakElement(int[] nums) {
        int low = 0;
        int high = nums.length - 1;
        if (high == 0) {return 0;
        }
        if (high == 1) {if (nums[0] < nums[1]) {return 1;
            }
            return 0;
        }

        while (low <= high){ / / 6,5,4,3,2,3,2 / / 5,4,3,4,5
            int mid = low + (high - low)/2;
            if (mid == 0) {return 0;
            }
            if (mid == nums.length - 1) {return mid;
            }

            if (nums[mid] > nums[mid - 1]) {/ / up hill
                if (mid == nums.length - 1) {return mid;
                }
                if (nums[mid] > nums[mid + 1]) {return mid;
                }
                // mid < mid + 1 //
                low = mid + 1;

            } else {  Nums [mid] < nums[mid - 1]
                if (mid == 1) {return 0;
                }
                if (mid >= 2 && nums[mid - 1] > nums[mid - 2]) {return mid - 1;
                }
                high = mid - 1; }}return -1;

    }
Copy the code

conclusion

Peak problems also have certain routines, as long as we are familiar with the dichotomy solution scenario, this kind of problems can be easily solved.