11. Rotate the smallest number in the array

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

1. Title 📑

Moving the beginning elements of an array to the end of the array is called array rotation.

You are given an array of numbers that may have duplicate elements. It was originally an array in ascending order, rotated once as described above. Return the smallest element of the rotated array. For example, the array [3,4,5,1,2] is a rotation of [1,2,3,4,5], whose minimum value is 1.

Example 1:

Input:,4,5,1,2 [3]

Output: 1.

Example 2:

Input:,2,2,0,1 [2]

Output: 0

Note:

  • The following is the same as the main station 154: leetcode-cn.com/problems/fi…

2. Ideas 🧠

Method 1: violent solution

  1. According to the meaning of the question, the first time to solve the problem through burst, use variables to record the minimum value encountered in the current traversal process, after traversal, return the minimum value.
  2. Why is violence not elegant, because we know that the array is being rotated, and as we go through it, as long as any number is less than, rightnumbers[0] , then the number must be the minimum.

Method two: binary optimization

Violence is not our goal to solve the problem, violence is not into the factory, so friends in doing the problem or to think about the optimization of the solution boil.

  1. Create two Pointers L and R to eachnumbersHead and tail, calculate the intermediate index value M between the two Pointers, the following three situations will occur:
  2. Let’s think about it separately
    • When M > R, the minimum must be to the right of M, so move L to M + 1.
    • When M is less than R, the minimum must be to the left of M, which is where M is, so let’s move R to where M is.
    • M is neither greater than the value of L nor less than the value of R, which means that M could be equal to the value of L, or the value of R, and the only way to keep going is to decrement R to find the minimum.

Less nonsense ~~~~~ on the code!

3. Code: 👨💻

Commit AC for the first time

class Solution {
    public int minArray(int[] numbers) {
        int i;
        int index = 0;
        for(i = 0; i < numbers.length -1; i++){
            if(numbers[i] >numbers[i + 1]) index = i + 1;
        }
        returnnumbers[index]; }}Copy the code

Time complexity: O(n)

Space complexity: O(1)

Commit the SECOND TIME

class Solution {
    public int minArray(int[] numbers) {
        int L = 0,R = numbers.length - 1;
        while(L < R){
            int M = L + ((R - L) >> 1);// This is a round down
            if(numbers[M] > numbers[R]) {
                L = M + 1;
            }
            else if(numbers[M] < numbers[R]) {
                R = M;
            }
            else R -= 1;
        }
        returnnumbers[L]; }}Copy the code

Time complexity: O(log 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!

11. Rotate the smallest number in the array