到目标元素的最小距离

标签: 数组

难度: Easy

给你一个整数数组 nums （下标 从 0 开始 计数）以及两个整数 target 和 start ，请你找出一个下标 i ，满足 nums[i] == target 且 abs(i - start) 最小化 。注意：abs(x) 表示 x 的绝对值。

返回 abs(i - start) 。

题目数据保证 target 存在于 nums 中。

 

示例 1：

输入：nums = [1,2,3,4,5], target = 5, start = 3
输出：1
解释：nums[4] = 5 是唯一一个等于 target 的值，所以答案是 abs(4 - 3) = 1 。

示例 2：

输入：nums = [1], target = 1, start = 0
输出：0
解释：nums[0] = 1 是唯一一个等于 target 的值，所以答案是 abs(0 - 0) = 0 。

示例 3：

输入：nums = [1,1,1,1,1,1,1,1,1,1], target = 1, start = 0
输出：0
解释：nums 中的每个值都是 1 ，但 nums[0] 使 abs(i - start) 的结果得以最小化，所以答案是 abs(0 - 0) = 0 。

 

提示：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 104
  • 0 <= start < nums.length
  • target 存在于 nums 中

Submission

运行时间: 20 ms

内存: 16.2 MB

from typing import List

class Solution:
    def getMinDistance(self, nums: List[int], target: int, start: int) -> int:
        min_distance = float('inf')  # 初始化最小距离为无穷大
        min_index = -1  # 用于记录找到目标值时的索引
        
        # 遍历数组，寻找目标值
        for i in range(len(nums)):
            if nums[i] == target:
                # 计算当前索引与起始索引的绝对值差
                distance = abs(i - start)
                # 如果当前距离比之前记录的最小距离小，则更新最小距离和索引
                if distance < min_distance:
                    min_distance = distance
                    min_index = i
                    
        # 由于题目保证目标值存在于数组中，所以min_index一定会被赋值，这里可以直接返回最小距离
        return min_distance

# 示例测试
solution = Solution()
print(solution.getMinDistance([1, 2, 3, 4, 5], 5, 3))  # 输出: 1
print(solution.getMinDistance([1], 1, 0))  # 输出: 0
print(solution.getMinDistance([1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 1, 0))  # 输出: 0

Explain

此题解通过遍历数组来寻找与目标值target相等的元素，并在此过程中计算并更新与起始位置start的最小绝对距离。对于数组中的每个元素，如果其值等于target，则计算其索引与start的绝对差值。如果这个差值小于当前记录的最小距离，则更新最小距离。遍历完成后，返回最小距离。由于题目保证target必在数组中出现，总会有一个有效的最小距离被返回。

时间复杂度: O(n)

空间复杂度: O(1)

from typing import List

class Solution:
    def getMinDistance(self, nums: List[int], target: int, start: int) -> int:
        min_distance = float('inf')  # 初始化最小距离为无穷大
        min_index = -1  # 记录找到目标值时的索引，虽然在这个算法中未被用到
        
        # 遍历数组，寻找目标值
        for i in range(len(nums)):
            if nums[i] == target:
                # 计算当前索引与起始索引的绝对值差
                distance = abs(i - start)
                # 如果当前距离比之前记录的最小距离小，则更新最小距离
                if distance < min_distance:
                    min_distance = distance
                    min_index = i  # 更新最近发现的索引
        
        # 返回记录的最小距离
        return min_distance

# 示例测试
solution = Solution()
print(solution.getMinDistance([1, 2, 3, 4, 5], 5, 3))  # 输出: 1
print(solution.getMinDistance([1], 1, 0))  # 输出: 0
print(solution.getMinDistance([1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 1, 0))  # 输出: 0

Explore

在提供的算法中，min_index确实被初始化了，但最终并没有在算法的任何关键功能中被使用。这可能是因为在最初的设计中考虑到了记录最近的目标值的位置，但后来发现仅需要计算最小距离就足够了。因此，这个变量可以被视为冗余，除非在未来的算法扩展中需要使用这个索引。

该算法通过遍历整个数组来查找每一个等于target的元素，并计算距离，因此它确实考虑了数组中可能存在多个目标值的情况。尽管这样会增加计算量，但这确保能找到与起始位置最近的目标值的最小距离。在效率方面，这种方法的时间复杂度为O(n)，其中n是数组的长度。对于数组中有多个目标值的情况，这是一个简单直接的解决方案，虽然在特定条件下可能存在更优化的方法。

是的，可以采用双向搜索等方法来可能提高搜索效率。例如，可以从数组的起始位置start同时向左和向右搜索，这样可以在遇到第一个target时立即停止搜索，可能在某些情况下减少搜索的总步数。这种方法特别适用于当target可能很靠近起始索引的一侧时。此外，如果数组是有序的，可以使用二分查找技术来快速定位到最近的target，进一步提高效率。然而，对于无序数组，双向搜索提供了一种相对平衡的方法来减少在最坏情况下的搜索次数。