面试题29：数组中出线次数超过一半的数字

    数组中有一个数字出线的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

思路1：

   对于有序的数组，出线次数超过一半的数字肯定会出现在数组中间的位置。

    对数组进行排列，然后直接输出排列后数组中间位置的数字

    注意：排序算法的使用——快速排序！

思路2：

    这个数字出线的次数比其他所有数字出线的次数和要多。

    遍历数组，保存两个值，一个数组中的一个数字，一个是次数。

    次数：初始为1。

    数字：初始为第一个值。

    当下一个数字与其前一个数字相同，则次数+1；否则次数-1；

    当次数为0时，下一个数字为保存数字。

    这样，最后保存的数字一定为所求数字~（它的次数大于其它所有数字的和）。

1 #include 
       
         2 using namespace std; 3 void QuickSort(int* arr,int left,int right); 4 int Partition(int* arr,int left,int right); 5 int MoreThanHalfNum1(int* arr,int len); 6 int MoreThanHalfNum2(int* arr,int len); 7 void Change(int &a,int &b) 8 { 9     int temp=a;10     a=b;11     b=temp;12 }13 int main()14 {15     const int mSize=20;16     int a[mSize]={
     1,2,3,2,2,2,5,4,2};17     int len=9;18 //    for(int i=0;i
       

 

面试题30：最小的k个数

    输入n个整数，找出其中最小的k个数。例如输入4、5、1、6、2、7、3、8这8个数字，则最小的4和数是1、2、3、4

思路1：

    排序，选择前k个数，时间复杂度为O(nlogn)，面试官可能不满意

    并且该方案改变了原来数组的结构（当然这不是问题）。

思路2：

    与29道思路二类似：

    遍历一边数组即可：定位arr[k]，遍历数组，所有比arr[k]小的数放在arr[k]左边，比它大的数放在其右边。这不类似于快速排序里面那个Partition嘛~

    具体实现：（基于Partition）

    我们知道，Partition得到的是一个值，小于这个值的都在其左边，大于这个值的都在其右边。

    而我们的目标是：小于arr[k-1]的都在其左边，而大于arr[k-1]的都在其右边，因此arr[0]-arr[k-1]就是所求的k个数

    这样的话，问题就简单了，只要Partition的返回值为k-1就行了。

    因此：如果Partition的返回值<k-1，则在其右侧继续进行Partition；而Partition的返回值>k-1，则在其左侧继续Partition

1 #include 
        
          2 using namespace std; 3 void Change(int &a,int &b) 4 { 5     int temp; 6     temp=a; 7     a=b; 8     b=temp; 9 }10 /// 方案1：先排序，直接找出排序后的前k个11 void GetLeastNumbers1(int* arr,int len,int k);12 int Partition(int* arr,int left,int right);13 void QuickSort(int* arr,int left,int right);14 15 ///方案2：基于Partition的方法16 void GetLeastNumbers2(int* arr,int len,int k);17 18 19 int main()20 {21     int arr[]={
      4,5,1,6,2,7,3,8};22     int k=4;23     int len=sizeof(arr)/sizeof(arr[0]);24 //    GetLeastNumbers1(arr,len,k);25     GetLeastNumbers2(arr,len,k);26     return 0;27 }28 29 ///1:30 int Partition(int* arr,int left,int right)31 {32     int i=left-1;33     for(int j=left;j
         
          right) return;47     if(left
         
        

 

1 ///3: 2 void GetLeastNumbers3(vector
        
          arr,int k) 3 { 4     vector
         
          ::iterator iter1=arr.begin(); 5     multiset
          
           
             > leastNumbers; 6     multiset
            
             
               >::iterator iter2; 7 for(;iter1!=arr.end();iter1++) 8 { 9 if((leastNumbers.size())
              

>::iterator temp=leastNumbers.begin();14 if(*iter1<*(leastNumbers.begin()))15 {16 leastNumbers.erase(temp);//删除顶端元素，最大堆中顶端元素就是最大的元素17 leastNumbers.insert(*iter1);18 }19 }20 }21 for(iter2=leastNumbers.begin();iter2!=leastNumbers.end();iter2++)22 cout<<*iter2<<" ";23 cout<