当前位置:网站首页>LeetCode 1200.最小绝对差
LeetCode 1200.最小绝对差
2022-07-05 05:45:00 【Tisfy】
【LetMeFly】1200.最小绝对差
力扣题目链接: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 <= 10^5
-10^6 <= arr[i] <= 10^6
方法一:排序
这道题的数据范围是 1 0 5 10^5 105,因此无法 O ( n 2 ) O(n^2) O(n2)暴力
其实也不难,因为排序后“最小绝对差的元素对”一定相邻
所以我们直接排序即可,然后进行两次遍历
第一次求出绝对值只差的最小值,第二次把绝对值之差等于最小值的pair放入答案中即可。
- 时间复杂度 O ( n log n ) O(n\log n) O(nlogn),其中 n n n 是数组 arr \textit{arr} arr 的长度
- 空间复杂度 O ( log n ) O(\log n) O(logn),皆为排序所至
AC代码
C++
class Solution {
public:
vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
sort(arr.begin(), arr.end());
int m = arr[1] - arr[0];
for (int i = 1; i < arr.size(); i++) {
m = min(m, arr[i] - arr[i - 1]);
}
vector<vector<int>> ans;
for (int i = 1; i < arr.size(); i++) {
if (arr[i] - arr[i - 1] == m) {
ans.push_back({
arr[i - 1], arr[i]});
}
}
return ans;
}
};
同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/125609898
边栏推荐
- SAP-修改系统表数据的方法
- Reader writer model
- How to adjust bugs in general projects ----- take you through the whole process by hand
- Implement a fixed capacity stack
- 网络工程师考核的一些常见的问题:WLAN、BGP、交换机
- Implement an iterative stack
- High precision subtraction
- Chapter 6 data flow modeling - after class exercises
- Transform optimization problems into decision-making problems
- kubeadm系列-02-kubelet的配置和启动
猜你喜欢
Support multi-mode polymorphic gbase 8C database continuous innovation and heavy upgrade
CF1634 F. Fibonacci Additions
[practical skills] technical management of managers with non-technical background
Web APIs DOM node
Remote upgrade afraid of cutting beard? Explain FOTA safety upgrade in detail
Hang wait lock vs spin lock (where both are used)
剑指 Offer 58 - II. 左旋转字符串
Sword finger offer 06 Print linked list from beginning to end
Graduation project of game mall
浅谈JVM(面试常考)
随机推荐
Sword finger offer 05 Replace spaces
每日一题-搜索二维矩阵ps二维数组的查找
After setting up the database and website When you open the app for testing, it shows that the server is being maintained
Use of room database
On the characteristics of technology entrepreneurs from Dijkstra's Turing Award speech
Educational codeforces round 109 (rated for Div. 2) C. robot collisions D. armchairs
Simple knapsack, queue and stack with deque
SAP-修改系统表数据的方法
【Jailhouse 文章】Jailhouse Hypervisor
Implement a fixed capacity stack
剑指 Offer 53 - II. 0~n-1中缺失的数字
[jailhouse article] performance measurements for hypervisors on embedded ARM processors
[jailhouse article] look mum, no VM exits
Annotation and reflection
Animation scoring data analysis and visualization and it industry recruitment data analysis and visualization
Acwing 4300. Two operations
In this indifferent world, light crying
Dichotomy, discretization, etc
Add level control and logger level control of Solon logging plug-in
常见的最优化方法