数组中的最小差异 [英] Minimum difference in an array
本文介绍了数组中的最小差异的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我想要找到一个数组的所有元素之间的最小差异。我阅读了各种其他问题,但无法找到错误的确切来源在以下代码。
I want to find the minimum difference among all elements of an array. I read through various other questions, but couldn't find the exact source of the error in the following code.
#include<iostream>
#include<stdio.h>
#include<cstdlib>
using namespace std;
void quicksort(long int *lp, long int *rp);
int main()
{
int t,n;
long int s[5000];
cin>>t;
while(t--){
cin>>n;
for(int i=0;i<n;i++) cin>>s[i];
quicksort(&s[0],&s[n-1]);
//cout<<"passes:"<<passes<<endl;
//for(int i=0;i<n;i++) cout<<s[i]<<" ";
long int min = abs(s[1]-s[0]);
//cout<<endl<<min;
for(int i=1;i<(n-1);i++){
long int temp = abs(s[i]-s[i+1]);
if (temp <= min) min = temp;
}
cout<<min;
}
}
void quicksort(long int *lp,long int *rp){
int arraysize= (rp-lp)+1;
if(arraysize > 1){
long int *pivot = (lp+(arraysize/2));
long int swap=0;
long int *orgl = lp;
long int *orgr = rp;
while(lp!=rp){
while (*lp < *pivot) lp++;
while (*rp > *pivot) rp--;
if (lp == pivot) pivot=rp;
else if (rp == pivot) pivot=lp;
swap = *lp;
*lp = *rp;
*rp = swap;
if((*lp == *pivot) || ( *rp == *pivot)) break;
}
quicksort(orgl,pivot-1);
quicksort(pivot+1,orgr);
}
}
问题陈述在此链接中提供: http://www.codechef.com/problems/HORSES
你能确定我的程序中的错误吗?
The problem statement is given in this link : http://www.codechef.com/problems/HORSES Can you please identify the error in my program ?
推荐答案
快速排序这不是真正保证O(n * logn)你最好使用排序从< algorithm>
。
这个逻辑看起来不错:
You are using C++ so instead of using your custom quicksort which is not really guarantee O(n*logn) you better use sort from <algorithm>
.
This logic looks good:
long int min = abs(s[1]-s[0]);
//cout<<endl<<min;
for(int i=1;i<(n-1);i++){
long int temp = abs(s[i]-s[i+1]);
if (temp <= min) min = temp;
}
By the way:
cout<<min;
Add cout<<min << endl;
这篇关于数组中的最小差异的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文