“This is the sixth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Related articles

LeetCode brush questions summary: LeetCode brush questions

1. Title Description

Magic indexes

Magic index. In array A[0…n-1], there is A so-called magic index that satisfies the condition A[I] = I. Given an ordered array of integers, write A method to find the magic index, if any, in array A. If none, return -1. If there are more than one magic index, return the smallest index value.

Second, train of thought analysis

  • Look at the examples in the title, let’s clarify the idea ~

  • Example 1:

    Input: nums = [0, 2, 3, 4, 5] Output: 0 Description: The element subscript 0 is 0Copy the code

  • Example 2:

    Input: nums = [1, 1, 1] Output: 1Copy the code

  • instructions

    • The nums is in the range of [1, 1000000]
    • This title is follow-up from the original book, which is the version of the array that may contain repeating elements

  • Same rule, follow your first instinct, brute force crack to a wave!

AC code

  • Brute force cracking:
class Solution { public int findMagicIndex(int[] nums) { for(int i=0; i<nums.length; i++){ if(i==nums[i]){ return i; } } return -1; }}Copy the code

  • Execution Result:

  • I don’t think we need to explain this, do we?

  • Jump search method:

    • This array is incremented and repeatable.

    • Num [I] must be greater than or equal to num[I -1].

    • If num[I] > I, then all the way up to num[I] is invalid.

    • For example:

      • Num [] =,2,3,8,9,11 {1};
      • num[1] = 2 > 1
      • Num [2] = 3 num[2] = 3 That’s a hundred percent ineligible
      • And so on
      • Num [3]=8 >3;

    • Perfect. Try it this way:

    • class Solution { public int findMagicIndex(int[] nums) { int i = 0; while (i < nums.length) { if (nums[i] == i) { return i; } else if (nums[I] > I) {if (nums[I] > I) {if (nums[I] > I); }else{ i++; } } return -1; }}Copy the code

    • Execution Result:

The road ahead is long, I see no end, I will search high and low

If you think I bloggers write well! Writing is not easy, please like, follow, comment and give encouragement to the blogger ~ Hahah