20200731-mst.08.03.magic-index-lcci.md

mst.08.03.magic-index-lcci

题目链接：https://leetcode-cn.com/problems/magic-index-lcci/

参考链接：https://leetcode-cn.com/problems/magic-index-lcci/solution/mo-zhu-suo-yin-by-leetcode-solution/

题目

魔术索引。 在数组A[0...n-1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。

示例1：

输入：nums = [0, 2, 3, 4, 5]
输出：0
说明: 0下标的元素为0

示例2：

输入：nums = [1, 1, 1]
输出：1

说明:

1. nums长度在[1, 1000000]之间
2. 此题为原书中的 Follow-up，即数组中可能包含重复元素的版本

解题

思路[1]暴力

• 遍历一遍，对比下标和元素

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMagicIndex = function(nums) {
  return nums.find((v, index) => v === index)??-1
};

思路[2]遍历跳跃

• 因为是有序数组，所以如果当前元素和当前下标不相等，则可以直接跳跃至当前元素的下标处判断，这样有概率较少遍历

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMagicIndex = function(nums) {
  let i=0
  while(i < nums.length){
    if (i==nums[i]){
      return i
    }    
    if (i<nums[i]) {
      i=nums[i]
    } else {
      i+=1
    }  
  }
      
  return -1
};

思路[3]二分法剪枝

• 先遍历左边，如果左边不存在再去找右边
• 如果数组中只有一个魔法元素则时间复杂度会减少，但有多个时，就需要先查找左边
• 官方提供的二分法感觉并不是最优的

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
const findMagicIndex = (nums) => {
  const find = (lo, hi) => {
    if (lo > hi) return -1;
    const mid = (lo + hi) >>> 1;
    const magicIndex = find(lo, mid - 1);
    if (magicIndex > -1) {
      return magicIndex;
    } else if (nums[mid] == mid) {
      return mid;
    } else {
      return find(mid + 1, hi);
    }
  };
  return find(0, nums.length - 1);
};

思考