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语言 ,

上一个：kemata处理
下一个：kemata处理