当前位置:网站首页>1200.Minimum Absolute Difference
1200.Minimum Absolute Difference
2022-07-07 03:26: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.
source : Power button (LeetCode)
link :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
边栏推荐
猜你喜欢
20.(arcgis api for js篇)arcgis api for js面采集(SketchViewModel)
华为小米互“抄作业”
Shangsilicon Valley JVM Chapter 1 class loading subsystem
存储过程与函数(MySQL)
Don't you know the relationship between JSP and servlet?
Appx代码签名指南
Open3D 网格滤波
VHDL实现单周期CPU设计
Decoration design enterprise website management system source code (including mobile source code)
从0开始创建小程序
随机推荐
校招行测笔试-数量关系
2022.6.28
杰理之在非蓝牙模式下,手机连接蓝牙不要跳回蓝牙模式处理方法【篇】
小程序能运行在自有App中,且实现直播和连麦?
Laravel php artisan 自动生成Model+Migrate+Controller 命令大全
编译常量、ClassLoader类、系统类加载器深度探析
Jericho is in non Bluetooth mode. Do not jump back to Bluetooth mode when connecting the mobile phone [chapter]
【colmap】已知相机位姿情况下进行三维重建
Cryptography series: detailed explanation of online certificate status protocol OCSP
Leetcode-02 (linked list question)
R数据分析:cox模型如何做预测,高分文章复现
When you go to the toilet, you can clearly explain the three Scheduling Strategies of scheduled tasks
杰理之关于 DAC 输出功率问题【篇】
DOMContentLoaded和window.onload
Sub pixel corner detection opencv cornersubpix
Make (convert) ICO Icon
函数重入、函数重载、函数重写自己理解
腾讯云原生数据库TDSQL-C入选信通院《云原生产品目录》
Principle of attention mechanism
SQL Tuning Advisor一个错误ORA-00600: internal error code, arguments: [kesqsMakeBindValue:obj]