当前位置:网站首页>leetcode:1200. Minimum absolute difference
leetcode:1200. Minimum absolute difference
2022-07-05 11:36:00 【uncle_ ll】
1200. Minimum absolute difference
source : Power button (LeetCode)
link : https://leetcode.cn/problems/minimum-absolute-difference
Here's an array of integers arr, Each of these elements is inequality .
Please find all the elements with the least absolute difference , And return in ascending order .
Example 1:
Input :arr = [4,2,1,3]
Output :[[1,2],[2,3],[3,4]]
Example 2:
Input :arr = [1,3,6,10,15]
Output :[[1,3]]
Example 3:
Input :arr = [3,8,-10,23,19,-4,-14,27]
Output :[[-14,-10],[19,23],[23,27]]
Tips :
- 2 <= arr.length <= 1 0 5 10^5 105
- − 1 0 6 -10^6 −106 <= arr[i] <= 1 0 6 10^6 106
solution
- Sort + Traverse : The difference between adjacent elements after sorting is the smallest absolute difference of the element , Traverse after sorting , If the absolute difference is less than the minimum absolute difference , Update absolute difference , Update results ; If it is equal to the minimum absolute difference , Add one result to the result ; If it is larger than, it will not be processed ;
Code implementation
Sort + Traverse
python Realization
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++ Realization
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;
}
};
Complexity analysis
- Time complexity : O ( N l o g N ) O(NlogN) O(NlogN) Sorting time
- Spatial complexity : O ( l o g N ) O(logN) O(logN) Space required for sorting
边栏推荐
- How can edge computing be combined with the Internet of things?
- DDoS attack principle, the phenomenon of being attacked by DDoS
- 居家办公那些事|社区征文
- COMSOL -- establishment of geometric model -- establishment of two-dimensional graphics
- How to make your products as expensive as possible
- 2048游戏逻辑
- AUTOCAD——遮罩命令、如何使用CAD对图纸进行局部放大
- Differences between IPv6 and IPv4 three departments including the office of network information technology promote IPv6 scale deployment
- 简单解决redis cluster中从节点读取不了数据(error) MOVED
- redis 集群模式原理
猜你喜欢
随机推荐
程序员内卷和保持行业竞争力
Sklearn model sorting
11.(地图数据篇)OSM数据如何下载使用
redis主从模式
pytorch训练进程被中断了
An error is reported in the process of using gbase 8C database: 80000305, host IPS long to different cluster. How to solve it?
redis集群中hash tag 使用
【Win11 多用户同时登录远程桌面配置方法】
Mysql统计技巧:ON DUPLICATE KEY UPDATE用法
百问百答第45期:应用性能探针监测原理-node JS 探针
FFmpeg调用avformat_open_input时返回错误 -22(Invalid argument)
Harbor镜像仓库搭建
MySQL 巨坑:update 更新慎用影响行数做判断!!!
comsol--三维图形随便画----回转
Prevent browser backward operation
1.php的laravel创建项目
[there may be no default font]warning: imagettfbbox() [function.imagettfbbox]: invalid font filename
龙蜥社区第九次运营委员会会议顺利召开
MySQL giant pit: update updates should be judged with caution by affecting the number of rows!!!
Spark Tuning (I): from HQL to code