两个未排序数组之间的最小差异 [英] Minimum difference between two unsorted arrays
问题描述
我必须找到未排序数组的两个元素之间的最小绝对差异。我的方法是首先对数组进行排序，在一个数组上运行一个循环，然后在另一个数组中找到该数组的每个元素的下限。
然后检查是否它是否最小化并存储以供进一步比较
测试案例：
2
8 1 3 5 7 9 7 3 1
8 2 4 6 8 10 8 6 2
8 2 3 5 10 9 3 2 1
7 1 2 6 12 13 3 2
输出：
1
0
结果：通过
说明：
1）min将是abs（a [7] -b [7]）
2）min将是abs（a [0] -b [（1）]）
但是当我提交给spoj时，我得到了错误的答案。
请帮忙！
问题链接： SPOJ.com - 问题ACPC11B [ ^ ]
我尝试过：
I have to find min absolute difference between two elements of unsorted arrays. My approach is to first sort both the array, run a loop over one array and find lower bound of each element of this array in another array.
And then check whether it is minimum or not and store it for further comparisons
Test Case:
2
8 1 3 5 7 9 7 3 1
8 2 4 6 8 10 8 6 2
8 2 3 5 10 9 3 2 1
7 1 2 6 12 13 3 2
Output :
1
0
result : passed
Explanation:
1) min will be abs(a[7]-b[7])
2) min will be abs(a[0]-b[(1)])
But when i am submitting to spoj I am getting wrong answer .
Please help!
Problem Link : SPOJ.com - Problem ACPC11B[^]
What I have tried:
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector <int> a;
vector <int> b;
int main(){
int t;
cin>>t;
while(t--){
int na;
cin>>na;
for(int i=0;i<na;i++){
int temp;
cin>>temp;
a.push_back(temp);
}
int nb;
cin>>nb;
for(int i=0;i<nb;i++){
int temp;
cin>>temp;
b.push_back(temp);
}
sort(a.begin(),a.end());
sort(b.begin(),b.end());
int ans=abs(a[0]-b[0]);
for(int i=0;i<a.size();i++){
int bval = lower_bound(b.begin(),b.end(),a[i])-b.begin();
ans = min(ans,abs(a[i]-b[bval]));
if(bval>0)
ans = min(ans,abs(a[i]-b[bval-1]));
}
cout<<ans<<endl;
a.clear();
b.clear();
}
}
推荐答案
查看要求（首先是所有约束条件），蛮力方法（两个嵌套循环）可以顺利运行。
关于你自己的代码，这部分
Looking at requirements (above all the constraints), a brute force approach (two nested loops) would work smoothly.
Regarding your own code, this part
int bval = lower_bound（b.begin（），b.end（），a [i]） - b.begin（）;
ans = min （ans，abs（a [i] -b [bval]））;
if（bval> 0）
ans = min（ans，abs（a [i ] -b [bval-1]））;
int bval = lower_bound(b.begin(),b.end(),a[i])-b.begin();
ans = min(ans,abs(a[i]-b[bval]));
if(bval>0)
ans = min(ans,abs(a[i]-b[bval-1]));
不正确。
它应该是
is incorrect.
It should be
size_t bval = lower_bound(b.begin(),b.end(),a[i])-b.begin();
if ( bval < b.size() )
ans = min(ans,abs(a[i]-b[bval]));
if(bval > 0)
ans = min(ans,abs(a[i]-b[bval-1]));
以新的开头奇数数据样本，看你的算法是如何表现的。
2
8 1 3 5 7 9 11 21 23
8 13 14 15 19 23 25 29 29
8 13 14 15 19 23 25 29 29
8 1 3 5 7 9 11 21 23
您是否找到了正确的答案？
你的代码没有你想象的那样，或者你不明白为什么！
有一个几乎通用的解决方案：逐步在调试器上运行代码，检查变量。
调试器在这里向您展示您的代码正在做什么，您的任务是与什么进行比较它应该这样做。
调试器中没有魔法，它不知道你的cpde应该做什么，它没有找到bug，它只是通过向你展示什么是帮助你继续当代码没有达到预期的效果时，你就接近了一个错误。
要查看你的代码在做什么：只需设置断点并查看代码是否正常运行，调试器允许你执行第1行第1行，并在执行时检查变量。
调试器 - 维基百科，免费的百科全书 [ ^ ]
掌握调试Visual Studio 2010 - 初学者指南 [ ^ ]
使用Visual Studio 2010进行基本调试 - YouTube [ ^ ]
1.11 - 调试程序（步进和断点）|学习C ++ [ ^ ]
调试器仅显示您的代码正在执行的操作，您的任务是与应该执行的操作进行比较。
[UpDate]
您可以通过删除此行来加快代码的速度
Start with new odd samples of data to see how your algorithm behave.
2
8 1 3 5 7 9 11 21 23
8 13 14 15 19 23 25 29 29
8 13 14 15 19 23 25 29 29
8 1 3 5 7 9 11 21 23
Do you find the correct answer ?
Your code do not behave the way you expect, or you don't understand why !
There is an almost universal solution: Run your code on debugger step by step, inspect variables.
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't know what your cpde is supposed to do, it don't find bugs, it just help you to by showing you what is going on. When the code don't do what is expected, you are close to a bug.
To see what your code is doing: Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.
Debugger - Wikipedia, the free encyclopedia[^]
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]
1.11 — Debugging your program (stepping and breakpoints) | Learn C++[^]
The debugger is here to only show you what your code is doing and your task is to compare with what it should do.
[UpDate]
You can make your code faster by removing this line
sort(a.begin(),a.end());
因为你的代码没有利用排序数组。
because your code don't take advantage of the sorted array.
这篇关于两个未排序数组之间的最小差异的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
