魔术索引

难度:

标签:

题目描述

A magic index in an array A[0...n-1] is defined to be an index such that A[i] = i. Given a sorted array of integers, write a method to find a magic index, if one exists, in array A. If not, return -1. If there are more than one magic index, return the smallest one.

Example1:

 Input: nums = [0, 2, 3, 4, 5]
 Output: 0

Example2:

 Input: nums = [1, 1, 1]
 Output: 1

Note:

1 <= nums.length <= 1000000
This problem is the follow-up of the original problem in the book, i.e. the values are not distinct.

代码结果

运行时间: 18 ms, 内存: 16.9 MB

// 思路: 使用Java Stream API，通过IntStream.range遍历数组并找到第一个满足A[i] = i的索引。
import java.util.OptionalInt;
import java.util.stream.IntStream;

public class MagicIndexStream {
    public int findMagicIndex(int[] nums) {
        OptionalInt magicIndex = IntStream.range(0, nums.length)
                                           .filter(i -> nums[i] == i)
                                           .findFirst();
        return magicIndex.orElse(-1);
    }
    public static void main(String[] args) {
        MagicIndexStream mis = new MagicIndexStream();
        int[] nums1 = {0, 2, 3, 4, 5};
        int[] nums2 = {1, 1, 1};
        System.out.println(mis.findMagicIndex(nums1)); // 输出: 0
        System.out.println(mis.findMagicIndex(nums2)); // 输出: 1
    }
}

解释

方法:

此题解采用了直接的线性搜索方法。从数组的第一个元素开始遍历，一旦发现某个索引i满足条件nums[i] == i，即判断为魔术索引，立即返回该索引。如果遍历完整个数组都没有找到符合条件的索引，则返回-1。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆

在有序数组中寻找特定条件的值时，为什么选择使用线性搜索而不是二分搜索来提高查找效率？

▷

在一般情况下，对于有序数组，二分搜索确实是一个更高效的选择。然而，对于魔术索引的查找问题，仅当数组元素严格递增且没有重复时，二分搜索才是有效的。这是因为二分搜索依赖于能够根据中间值的比较排除一半的搜索区域。如果数组中包含重复元素，这个条件可能会被破坏，因为即使中间元素不满足条件，满足条件的元素可能位于任何一侧。因此，在不确定数组特性的情况下，使用线性搜索是一种保证找到魔术索引的可靠方法，尽管其时间复杂度较高。

🦆

对于含有重复元素的数组，线性搜索方法在遇到重复值时能够有效地找到最小的魔术索引吗？

▷

线性搜索方法从数组的起始位置向后遍历，一旦找到满足条件的索引即返回，因此它能保证找到的是最小的魔术索引。即使数组中有重复元素，此方法仍然有效，因为它总是返回第一个找到的满足 nums[i] == i 的索引。

🦆

如果数组中的元素值大于当前索引值，线性搜索是否还需要继续向后查找？

▷

即使当前元素的值大于其索引，线性搜索还是需要继续向后查找。这是因为后续的索引值增加，可能存在某个更大的索引i，使得 nums[i] == i。只有当确定后面不可能存在满足条件的索引时（例如在某种特定的数组结构中），才可以提前终止搜索。但在一般情况下，不能因为当前元素值大于索引就停止搜索。

魔术索引

题目描述

代码结果

解释

代码细节讲解

相关问题