找出數組中和為N的一對數
/*
find the pair in an array .... that sum up to particular number
Company:Linkedin
Date:8/11/2011
*/
#include <iostream>
#include <cstdlib>
#include <ctime>
int randomPartition(int A[], int low, int high);
void quickSort(int A[],int low, int high);
bool findPair(int A[],int size,int sum,std::pair<int,int>& result);
void quickSort(int A[], int low, int high)
{
if(low>=high)
return;
int pivot=randomPartition(A,low,high);
quickSort(A,low,pivot-1);
quickSort(A,pivot+1,high);
}
int randomPartition(int A[], int low, int high)
{
srand(time((int)0));
int index=low+rand()%(high-low+1);
int t=A[high];
A[high]=A[index];
A[index]=t;
int key=A[high];
int i=low-1;
for(int j=low; j<high;j++)
{
if(A[j]<=key)
{
i++;
int t=A[i];
A[i]=A[j];
A[j]=t;
}
}
i++;
t=A[high];
A[high]=A[i];
A[i]=t;
return i;
}
bool findPair(int A[],int size,int sum,std::pair<int,int>& result)
{
quickSort(A,0,size-1);
int i=0;
int j=size-1;
while(i<j)
{
if(A[i]+A[j]==sum)
{
result.first=A[i];
result.second=A[j];
return true;
}
else if(A[i]+A[j]<sum)
i++;
else
j--;
}
return false;
}
void main()
{
int A[10]={-2,-5,1,4,3,9,6,5,7,0};
int sum;
std::cout<<"Please enter a sum value\n";
std::cin>>sum;
std::pair<int,int> result(0,0);
if(findPair(A,10,sum,result))
std::cout<<result.first<<"+"<<result.second<<" = "<<sum<<"\n";
else
std::cout<<"No pair found\n";
}
本文出自 “面試” 博客
