当前位置:网站首页>leetcode:1200. 最小绝对差
leetcode:1200. 最小绝对差
2022-07-05 09:43:00 【uncle_ll】
1200. 最小绝对差
来源:力扣(LeetCode)
链接: https://leetcode.cn/problems/minimum-absolute-difference
给你个整数数组 arr,其中每个元素都 不相同。
请你找到所有具有最小绝对差的元素对,并且按升序的顺序返回。
示例 1:
输入:arr = [4,2,1,3]
输出:[[1,2],[2,3],[3,4]]
示例 2:
输入:arr = [1,3,6,10,15]
输出:[[1,3]]
示例 3:
输入:arr = [3,8,-10,23,19,-4,-14,27]
输出:[[-14,-10],[19,23],[23,27]]
提示:
- 2 <= arr.length <= 1 0 5 10^5 105
- − 1 0 6 -10^6 −106 <= arr[i] <= 1 0 6 10^6 106
解法
- 排序+遍历: 排序后相邻元素的差就是该元素的最小的绝对差,排序之后进行遍历,如果绝对差小于最小绝对差,更新绝对差,更新结果;如果等于最小绝对差,结果中增加一个结果即可;大于的话不进行处理;
代码实现
排序+遍历
python实现
class Solution:
def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
n = len(arr)
res = []
arr.sort()
min_diff = float('inf')
for i in range(1, n):
if arr[i] - arr[i-1] < min_diff:
res = [[arr[i-1], arr[i]]]
min_diff = arr[i] - arr[i-1]
elif arr[i] - arr[i-1] == min_diff:
res.append([arr[i-1], arr[i]])
return res
c++实现
class Solution {
public:
vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
int n = arr.size();
vector<vector<int>> res;
sort(arr.begin(), arr.end());
int min_diff = INT_MAX;
for (int i=1; i<n; i++) {
if (arr[i]-arr[i-1] < min_diff){
res = {
{
arr[i-1], arr[i]}};
min_diff = arr[i] - arr[i-1];
}
else if (arr[i]-arr[i-1] == min_diff)
res.push_back({
arr[i-1], arr[i]});
}
return res;
}
};
复杂度分析
- 时间复杂度: O ( N l o g N ) O(NlogN) O(NlogN) 排序耗时
- 空间复杂度: O ( l o g N ) O(logN) O(logN) 排序需要的空间
边栏推荐
- Analysis on the wallet system architecture of Baidu trading platform
- Apache DolphinScheduler 系统架构设计
- The essence of persuasion is to remove obstacles
- 善用兵者,藏于无形,90 分钟深度讲解最佳推广价值作品
- 单片机原理与接口技术(ESP8266/ESP32)机器人类草稿
- A high density 256 channel electrode cap for dry EEG
- 一个程序员的职业生涯到底该怎么规划?
- Observation cloud and tdengine have reached in-depth cooperation to optimize the cloud experience of enterprises
- [app packaging error] to proceed, either fix the issues identified by lint, or modify your build script as follow
- How to correctly evaluate video image quality
猜你喜欢
【 conseils 】 obtenir les valeurs des axes X et y de la fonction cdfplot dans MATLAB
QT timer realizes dynamic display of pictures
Uni app running to wechat development tool cannot Preview
Hard core, have you ever seen robots play "escape from the secret room"? (code attached)
【小技巧】获取matlab中cdfplot函数的x轴,y轴的数值
基于单片机步进电机控制器设计(正转反转指示灯挡位)
A high density 256 channel electrode cap for dry EEG
How Windows bat script automatically executes sqlcipher command
The writing speed is increased by dozens of times, and the application of tdengine in tostar intelligent factory solution
ArcGIS Pro creating features
随机推荐
A high density 256 channel electrode cap for dry EEG
C#函数返回多个值方法
. Net delay queue
Kotlin compose multiple item scrolling
Matrix processing practice
Charm of code language
(1) Complete the new construction of station in Niagara vykon N4 supervisor 4.8 software
Tianlong Babu TLBB series - single skill group injury
mysql80服务不启动
The writing speed is increased by dozens of times, and the application of tdengine in tostar intelligent factory solution
MySQL数字类型学习笔记
Apache DolphinScheduler 系统架构设计
Applet image height adaptation and setting text line height
天龙八部TLBB系列 - 单体技能群伤
From "chemist" to developer, from Oracle to tdengine, two important choices in my life
Swift saves an array of class objects with userdefaults and nssecurecoding
Cent7 Oracle database installation error
@SerializedName注解使用
TDengine × Intel edge insight software package accelerates the digital transformation of traditional industries
Coffeescript Chinese character to pinyin code