题目: 有 n 个数, 两两组成二元组, 相差最小的有多少对呢? 相差最大呢?
例如 ar[] = {1,3,4,9}, 返回 1 1
br[] = {1,2,3,10,12,21}, 返回 2 1
我的思路是将元素两两做差, 将差值保存在一个数组内, 把数组进行排序, 即可找出最小差值多少个, 最大差值多少个.(看起来我的时间空间复杂度低不了)
- #include<iostream>
- #include<algorithm>
- #include<vector>
- using namespace std;
- void func(int n, int ar[], int br[])
- {
- int size = (n*n-n)/2;
- vector<int> vec;
- for(int i=0; i<n-1; ++i)
- {
- for(int j=i+1; j<n; ++j)
- {
- if(ar[i]>ar[j])
- vec.push_back(ar[i]-ar[j]);
- else
- vec.push_back(ar[j]-ar[i]);
- }
- }
- sort(vec.begin(), vec.end());
- for(auto i=vec.begin(); i!=vec.end(); ++i)
- cout<<*i<<" ";
- cout<<endl;
- cout<<"vec.size() ="<<vec.size()<<endl;
- if(vec[0] != vec[size-1])
- {
- int min = 0, max = 0;
- int i = 0;
- while(vec[i] == *vec.begin())
- {++min;++i;}
- i = size-1;
- while(vec[i] == vec[size-1])
- {++max; --i;}
- br[0] = min;
- br[1] = max;
- return;
- }
- br[0] = size;
- br[1] = size;
- return;
- }
- int main()
- {
- int ar[] = {1,2,3,4,5,6,7,8,9,0,234, -132, 354325, 52354, 123}, br[2]={0};
- func(sizeof(ar)/sizeof(ar[0]), ar, br);
- cout<<br[0]<<" "<<br[1]<<endl;
- return 0;
- }
运行结果
因该还有更好地思路来节省空间时间
于是我换了一种思路, 在每次拿到差值的时候就比较它是不是最大或最小值, 是就计数, 不是就跳过得到下面的算法
- #include<iostream>
- #include<algorithm>
- #include<vector>
- using namespace std;
- void func(int n, int ar[], int br[])
- {
- int min = -1, max = -1, maxc = 0, minc = 0, tmp = 0;
- for(int i=0; i<n-1; ++i)
- {
- if(!i)
- min = ((ar[0]-ar[1])>0 ? ar[0]-ar[1] : ar[1]-ar[0]);
- for(int j=i+1; j<n; ++j)
- {
- tmp = ar[i]-ar[j];
- if(tmp<0)
- tmp = -tmp;
- if(tmp<min){min=tmp;minc=1;continue;}
- else if(tmp==min){++minc;continue;}
- else if(tmp>max){max=tmp;maxc=1;continue;}
- else if(tmp==max){++maxc;continue;}
- else continue;
- }
- }
- br[0]=minc;
- br[1]=maxc;
- }
- int main()
- {
- int ar[] = {1,2,3,4,5,6,7,8,9,0,234, -132, 354325, 52354, 123}, br[2]={0};
- func(sizeof(ar)/sizeof(ar[0]), ar, br);
- cout<<br[0]<<" "<<br[1]<<endl;
- return 0;
- }
执行结果
看起来节省了空间
来源: http://www.bubuko.com/infodetail-3340154.html