剑指Offer28 最小的K个数(Partition函数应用+大顶堆)

包含了Partition函数的多种用法

以及大顶堆操作

 /*************************************************************************
     > File Name: 28_KLeastNumbers.cpp
     > Author: Juntaran
     > Mail: [e-mail]
     > Created Time: 2016年08月31日 星期三 19时45分41秒
  ************************************************************************/

 #include <stdio.h>
 #include <bits/stdc++.h>

 using namespace std;

 // 大顶堆求最小K个数
 typedef multiset<int, greater<int> > intSet;
 typedef multiset<int, greater<int> >::iterator setIterator;

 void GetKLeastNumbers2(int* data, intSet& leastNumbers, int length, int k)
 {
     leastNumbers.clear();

     if (k< || length<k)
         return;

     for (int i = ; i < length; ++i)
     {
         if (leastNumbers.size() < k)
             leastNumbers.insert(data[i]);

         else
         {
             setIterator Greatest = leastNumbers.begin();
             if (data[i] < *(leastNumbers.begin()))
             {
                 leastNumbers.erase(Greatest);
                 leastNumbers.insert(data[i]);
             }
         }
     }

     for (setIterator iter = leastNumbers.begin(); iter != leastNumbers.end(); ++iter)
     {
         printf("%d ", *iter);
     }
     printf("\n");
 }

 void swap(int* p, int* q)
 {
     int temp = *p;
     *p = *q;
     *q = temp;
 }

 // Partition函数应用
 int Partition(int* data, int length, int start, int end)
 {
     if (data==NULL || length<= || start< || end>=length)
         return -;

     // 令数组第一个数字为标杆
     int index = start;                

     // 标杆与数组最后一个元素交换
     swap(&data[index], &data[end]);

     int small = start - ;
     for (index = start; index < end; ++index)
     {
         if (data[index] < data[end])
         {
             ++ small;
             if (small != index)
             {
                 swap(&data[index], &data[small]);
             }
         }
     }
     ++ small;
     swap(&data[small], &data[end]);

     return small;
 }

 // 利用Partiton实现快排
 void quickSort(int* data, int length, int start, int end)
 {
     if (start==end || data==NULL || length<=)
         return;

     int index = Partition(data, length, start, end);
     // printf("index is %d\n", index);
     if (index > start)
         quickSort(data, length, start, index-);
     if (index < end)
         quickSort(data, length, index+, end);
 }

 // 利用Partition寻找出现次数超过一半的数 (中位数)
 int GetMoreThanHalf(int* input, int length)
 {
     if (input==NULL || length<=)
         return -;
     int start = ;
     int end   = length - ;
     int index = Partition(input, length, start, end);
     int middle = length >> ;
     while (index != middle)
     {
         if (index > middle)
         {
             end = index - ;
             index = Partition(input, length, start, end);
         }
         else
         {
             start = index + ;
             index = Partition(input, length, start, end);
         }
     }
     int ret = input[middle];
     // 检验是否正确
     int count2 = ;
     for (int i = ; i < length; ++i)
     {
         if (input[i] == ret)
             count2 ++;
     }
     if (count2* > length)
     {
         printf("middle number is %d\n", input[middle]);
         return ret;
     }
     else
     {
         printf("Not Find\n");
         return -;
     }
 }

 // 利用Partition寻找第K小的数
 int GetKthNumber(int* input, int length, int k)
 {
     if (input==NULL || length<= || k<= || k>length)
         return -;
     int start = ;
     int end   = length - ;
     int index = Partition(input, length, start, end);
     while (index != k - )
     {
         if (index > k-)
         {
             end = index-;
             index = Partition(input, length, start, end);
         }
         else
         {
             start = index + ;
             index = Partition(input, length, start, end);
         }
     }
     printf("Kth is %d\n", input[index]);
     return input[index];
 }

 // 利用Partition寻找最小K个数
 void GetKLeastNumbers(int* input, int length, int* output, int k)
 {
     if (input==NULL || output==NULL || length<= || k<= || k>length)
     {
         return;
     }
     int start = ;
     int end   = length - ;
     int index = Partition(input, length, start, end);
     while (index != k - )
     {
         if (index > k-)
         {
             end = index - ;
             index = Partition(input, length, start, end);
         }
         else
         {
             start = index + ;
             index = Partition(input, length, start, end);
         }
         // printf("index is %d\n", index);
     }
     for (int i = ; i < k; ++i)
         output[i] = input[i];

     for (int i = ; i < k; ++i)
         printf("%d ", output[i]);
     printf("\n");
 }

 int main()
 {
     int k = ;
     int nums[] = {,,,,,,,,,};
     int length = ;
     int output[k] = {};

     // 快速排序
     quickSort(nums, length, , length-);
     for (int i = ; i < length; ++i)
         printf("%d ", nums[i]);
     printf("\n");

     // 求最小K个数
     GetKLeastNumbers(nums, length, output, k);

     // 求第K大的数
     GetKthNumber(nums, length, k);

     // 求数组中超过一半的数(中位数)
     GetMoreThanHalf(nums, length);

     // 大顶堆求最小K个数
     intSet leastNumbers;
     GetKLeastNumbers2(nums, leastNumbers, length, k);
 }