Linkedin面试题

找出数组中和为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";
}
本文出自 “面试” 博客

补充：软件开发 , C语言 ,

上一个：float有效位数
下一个：kemata处理