值相等的最小索引

难度: Easy

给你一个下标从 0 开始的整数数组 nums ，返回 nums 中满足 i mod 10 == nums[i] 的最小下标 i ；如果不存在这样的下标，返回 -1 。

x mod y 表示 x 除以 y 的余数。

示例 1：

输入：nums = [0,1,2]
输出：0
解释：
i=0: 0 mod 10 = 0 == nums[0].
i=1: 1 mod 10 = 1 == nums[1].
i=2: 2 mod 10 = 2 == nums[2].
所有下标都满足 i mod 10 == nums[i] ，所以返回最小下标 0

示例 2：

输入：nums = [4,3,2,1]
输出：2
解释：
i=0: 0 mod 10 = 0 != nums[0].
i=1: 1 mod 10 = 1 != nums[1].
i=2: 2 mod 10 = 2 == nums[2].
i=3: 3 mod 10 = 3 != nums[3].
2 唯一一个满足 i mod 10 == nums[i] 的下标

示例 3：

输入：nums = [1,2,3,4,5,6,7,8,9,0]
输出：-1
解释：不存在满足 i mod 10 == nums[i] 的下标

示例 4：

输入：nums = [2,1,3,5,2]
输出：1
解释：1 是唯一一个满足 i mod 10 == nums[i] 的下标

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 9

Submission

运行时间: 22 ms

内存: 16.1 MB

from typing import List

class Solution:
    def smallestEqual(self, nums: List[int]) -> int:
        for i in range(len(nums)):
            if i % 10 == nums[i]:
                return i
        return -1

solution = Solution()
nums = [4, 3, 2, 1]
result = solution.smallestEqual(nums)
print(result)  # 输出: 2

Explain

此题解采用了直接的遍历方法来查找满足条件的最小索引。遍历整数数组 nums，对于每个索引 i，检查 i mod 10 是否等于 nums[i]。如果找到符合条件的索引，立即返回该索引值；如果遍历完成后没有找到任何符合条件的索引，返回 -1。

时间复杂度: O(n)

空间复杂度: O(1)

from typing import List

class Solution:
    def smallestEqual(self, nums: List[int]) -> int:
        # 遍历数组 nums
        for i in range(len(nums)):
            # 检查 i mod 10 是否等于 nums[i]
            if i % 10 == nums[i]:
                # 如果满足条件，返回索引 i
                return i
        # 如果没有找到符合条件的索引，返回 -1
        return -1

solution = Solution()
nums = [4, 3, 2, 1]
result = solution.smallestEqual(nums)
print(result)  # 输出: 2

Explore

题解中使用的线性遍历方法确实是最优的，因为每个元素都需要被检查以确定是否满足条件 'i % 10 == nums[i]'。由于这种条件直接依赖于索引和元素值，不存在更快的查找方法或使用其他数据结构来预先过滤或减少需要检查的元素数量。因此，在这种情况下，线性遍历是最直接且有效的方法。

在这种特定算法中，不存在数组索引越界的风险。算法中的遍历使用 `i` 从 0 到 `len(nums) - 1`，这正好是数组 `nums` 的有效索引范围。同时，`i % 10` 的结果总是介于 0 到 9 之间，这与数组索引无关，因此不会引起任何越界问题。

如果数组 `nums` 非常大，算法的时间复杂度为 O(n)，这意味着处理时间与数组大小成线性关系。虽然这是最优解，但对于非常大的数组，执行时间可能较长。考虑到这一点，可以尝试一些优化，如使用多线程或并发来同时检查数组的不同部分。然而，这些方法可能会增加实现的复杂度，并且并不总是可行的，特别是在资源受限或环境不支持并行处理的情况下。

返回 `-1` 通常是标准的方式来表示在数组中未找到符合特定条件的元素。这种方法简单且通用，适用于大多数情况。然而，根据具体应用场景，可能需要更复杂的错误处理或信息反馈机制。例如，可以返回一个错误对象或异常，提供更详细的错误信息，或者在API设计中包含状态码来描述不同的错误情况。不过，对于大多数算法实现而言，简单返回 `-1` 已足够表明查找失败的情况。