当前位置:网站首页>1200.Minimum Absolute Difference
1200.Minimum Absolute Difference
2022-07-06 20:18:00 【SUNNY_CHANGQI】
The description of the problem
Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements.
return a list of parirs in ascending order (with respect to pairs), each pair [a, b] follows.
1. a, b are from arr
2. a < b
3. b - a equals to the minimum absolute difference of any two elements in arr.
an example
Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/minimum-absolute-difference
The solution 1
The intuition
Leverage the loop nesting to traveral all the diffVal and store them into a map and log the minimum difference value. In the end, sort out the return nesting loop.
The corresponding codes
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
#include <map>
using namespace std;
class Solution {
public:
vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
vector<vector<int>> res;
map<int, vector<vector<int>>> m;
int minDiff = INT_MAX;
for (int i = 0; i < arr.size(); i++) {
for (int j = i + 1; j < arr.size(); j++) {
int diff = abs(arr[i] - arr[j]);
minDiff = min(minDiff, diff);
vector<int> t;
if (arr[i] < arr[j]) {
t.push_back(arr[i]);
t.push_back(arr[j]);
} else {
t.push_back(arr[j]);
t.push_back(arr[i]);
}
m[diff].push_back(t);
}
}
res = m[minDiff];
// sort res by first element
sort(res.begin(), res.end(), [](vector<int>& a, vector<int>& b) {
return a[0] < b[0];
});
return res;
}
};
int main()
{
Solution s;
vector<int> arr = {
4, 2, 1, 3};
vector<vector<int>> res = s.minimumAbsDifference(arr);
for (auto& v : res) {
for (auto& i : v) {
cout << i << " ";
}
cout << endl;
}
return 0;
}
The result
The solution 2
firstly sort out the elements in arr in asecending order. traversal the arr to find the minimum difference value. Lastly, traversal the second time.
The codes
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
#include <map>
using namespace std;
class Solution {
public:
vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
vector<vector<int>> res;
int minDiff = INT_MAX;
sort(arr.begin(), arr.end());
for (int i = 0; i < arr.size() - 1; i++) {
int diff = arr[i + 1] - arr[i];
minDiff = min(minDiff, diff);
}
for (auto it = arr.begin(); it != arr.end() - 1; it++) {
if (abs(*(it + 1) - *it) == minDiff) {
res.push_back({
*it, *(it + 1)});
}
}
return res;
}
};
int main()
{
Solution s;
vector<int> arr = {
4, 2, 1, 3};
vector<vector<int>> res = s.minimumAbsDifference(arr);
for (auto& v : res) {
for (auto& i : v) {
cout << i << " ";
}
cout << endl;
}
return 0;
}
The corresponding results
The more optimized solution
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
#include <map>
using namespace std;
class Solution {
public:
vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
vector<vector<int>> res;
int minDiff = INT_MAX;
sort(arr.begin(), arr.end());
for (int i = 0; i < arr.size() - 1; i++) {
int diff = arr[i + 1] - arr[i];
if (diff < minDiff) {
minDiff = diff;
res.clear();
res.push_back({
arr[i], arr[i + 1]});
} else if (diff == minDiff) {
res.push_back({
arr[i], arr[i + 1]});
}
}
return res;
}
};
int main()
{
Solution s;
vector<int> arr = {
4, 2, 1, 3};
vector<vector<int>> res = s.minimumAbsDifference(arr);
for (auto& v : res) {
for (auto& i : v) {
cout << i << " ";
}
cout << endl;
}
return 0;
}
The corresponding result
边栏推荐
- mos管實現主副電源自動切換電路,並且“零”壓降,靜態電流20uA
- [colmap] 3D reconstruction with known camera pose
- 密码学系列之:在线证书状态协议OCSP详解
- Flink task exit process and failover mechanism
- Not All Points Are Equal Learning Highly Efficient Point-based Detectors for 3D LiDAR Point
- cocos3——8. Implementation Guide for beginners
- 杰理之在非蓝牙模式下,手机连接蓝牙不要跳回蓝牙模式处理方法【篇】
- 【Swift】学习笔记(一)——熟知 基础数据类型,编码风格,元组,主张
- 你知道电子招标最突出的5大好处有哪些吗?
- netperf 而网络性能测量
猜你喜欢
VHDL实现单周期CPU设计
centerX: 用中国特色社会主义的方式打开centernet
How to analyze fans' interests?
Not All Points Are Equal Learning Highly Efficient Point-based Detectors for 3D LiDAR Point
【基于 RT-Thread Studio的CPK-RA6M4 开发板环境搭建】
杰理之在非蓝牙模式下,手机连接蓝牙不要跳回蓝牙模式处理方法【篇】
The latest 2022 review of "small sample deep learning image recognition"
mos管实现主副电源自动切换电路,并且“零”压降,静态电流20uA
RestClould ETL 社区版六月精选问答
Starting from 1.5, build a micro Service Framework -- log tracking traceid
随机推荐
【无标题】
unrecognized selector sent to instance 0x10b34e810
Uniapp adaptation problem
Use of tensorboard
杰理之播内置 flash 提示音控制播放暂停【篇】
Simple bubble sort
Numpy中排序操作partition,argpartition,sort,argsort
Shell programming basics
Hazel engine learning (V)
The version control of 2021 version is missing. Handling method
Laravel php artisan 自动生成Model+Migrate+Controller 命令大全
HMS core machine learning service creates a new "sound" state of simultaneous interpreting translation, and AI makes international exchanges smoother
Codeforces Round #264 (Div. 2) C Gargari and Bishops 【暴力】
杰理之FM 模式单声道或立体声选择设置【篇】
leetcode
如何替换模型的骨干网络(backbone)
应用程序启动速度的优化
Cryptography series: detailed explanation of online certificate status protocol OCSP
Intelligent static presence detection scheme, 5.8G radar sensing technology, human presence inductive radar application
sshd[12282]: fatal: matching cipher is not supported: [email protected] [preauth]