菊厂0510面试手撕题目解答
题目
输入一个整数数组，返回该数组中最小差出现的次数。
示例1：输入：[1,3,7,5,9,12]，输出：4，最小差为2，共出现4次；
示例2：输入：[90,98,90,90,1,1]，输出：4，最小差为0，其中[1,1]出现1次，[90,90,90]两两相减，共出现3次；
解题思路
优解
思路与代码
-
排序数组：使用内置的排序方法对数组进行排序。
-
计算相邻差值：遍历排序后的数组，计算相邻元素的差值，并存储在列表
diffs中。 -
确定最小差值：使用
min函数找到diffs中的最小值。 -
处理最小差值为0的情况：遍历排序后的数组，统计连续相同元素的组，并计算每组贡献的对数。连续重复元素的组的对数计算公式为
k*(k-1)/2，其中k是该组的元素个数。 -
处理最小差值不为0的情况：直接统计相邻差值等于最小差值的次数，使用
count方法实现。
这种方法通过排序和线性遍历，确保了时间复杂度为O(n log n)，适用于较大的数组。
def min_diff_count(nums):nums.sort()n = len(nums)if n < 2:return 0diffs = [nums[i] - nums[i-1] for i in range(1, n)]min_diff = min(diffs)if min_diff == 0:total = 0current_count = 1for i in range(1, n):if nums[i] == nums[i-1]:current_count += 1else:if current_count >= 2:total += current_count * (current_count - 1) // 2current_count = 1# 处理最后一个可能的连续组if current_count >= 2:total += current_count * (current_count - 1) // 2return totalelse:return diffs.count(min_diff)# nums = [1, 3, 5, 7, 9, 12]
nums = [90, 98, 90, 90, 1, 1]
print(min_diff_count(nums))暴力解
思路与代码
-
初始化：定义最小差值为无穷大（
float('inf')），计数器初始化为0。 -
遍历所有元素对：使用双重循环遍历所有可能的元素对（
i < j），避免重复计算。 -
计算绝对差：对于每对元素，计算它们的绝对差。
-
更新最小差值和计数：
-
如果当前差值小于已知最小差值，则更新最小差值，并将计数器重置为1。
-
如果当前差值等于已知最小差值，则计数器加1。
-
-
返回结果：最终返回最小差值出现的次数。
-
示例1：输入
[1, 3, 7, 5, 9, 12]，输出为4。 -
示例2：输入
[90, 98, 90, 90, 1, 1]，输出为4。 -
极端案例：输入
[1, 1, 1]，输出为3（所有两两对的差均为0）。
此方法的时间复杂度为 O(n^2)，适用于小规模数据。对于大规模数据，推荐使用排序后相邻元素差值的优化方法。
def min_diff_count_brute_force(nums):n = len(nums)if n < 2:return 0min_diff = float('inf')count = 0for i in range(n):for j in range(i + 1, n):diff = abs(nums[i] - nums[j])if diff < min_diff:# 发现更小的差值，重置计数min_diff = diffcount = 1elif diff == min_diff:# 差值等于当前最小值，增加计数count += 1return count# nums = [1, 3, 5, 7, 9, 12]
nums = [90, 98, 90, 90, 1, 1]
print(min_diff_count_brute_force(nums))