題目
輸入一個整數數組，返回該數組中最小差出現的次數。
示例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))
)
