//快速排序：Partition分割函数，三数中值分割
bool g_bInvalidInput = false;
int median3(int* data, int start, int end){
int middle = (start + end) >> 1;
if (data[start] > data[middle])
std::swap(data[start], data[middle]);
if (data[start] > data[end])
std::swap(data[start], data[end]);
if (data[middle] > data[end])
std::swap(data[middle], data[end]);
std::swap(data[middle], data[end - 1]);
return data[end - 1];
}
int Partition(int* data, int length, int start, int end){
if (data == nullptr || length <=0 ||start < 0 || end > length - 1){
g_bInvalidInput = true;
return 0;
}
int pivot = median3(data, start, end);
int i = start;
int j = end - 1;
for (;;){
while (data[++i] < pivot) {;}
while (data[--j] > pivot) {;}
if (i < j)
std::swap(data[i], data[j]);
else
break;
}
std::swap(data[i], data[end - 1]);
return i;
}
void QuickSort(int* data, int length, int start, int end){
if (start == end)
return;
int pivotIdx = Partition(data, length, start, end);
if (pivotIdx > start){
QuickSort(data, length, start, pivotIdx - 1);
}
if (pivotIdx < end){
QuickSort(data, length, pivotIdx + 1, end);
}
}
void QuickSortPort(int* data, int length){
if (data == nullptr || length <= 0)
return;
QuickSort(data, length, 0, length - 1);
}
//快速排序：随机选取枢纽元, Partition分割函数
#include <stdlib.h>
#include <time.h>
int randomInRange(int start, int end){
srand((unsigned int)(time(NULL)));
if (start == end)
return start;
else if (end < start)
return end + rand() % (start - end + 1);
else {
return start + rand() % (end - start + 1);
}
}
bool g_bInvalidInput = false;
int Partition(int* data, int length, int start, int end){
if (data == nullptr || length <= 0 || start < 0 || end > length - 1){
g_bInvalidInput = true;
return 0;
}
int pivotIdx = randomInRange(start, end);
int pivot = data[pivotIdx];
std::swap(data[pivotIdx], data[end]);
int i = start - 1;
int j = end;
for (; i <= end && j >= start; ){
while (++i <= end && data[i] < pivot) {;}
while (--j >=start && data[j] > pivot) {;}
if (i < j){
std::swap(data[i], data[j]);
}
else
break;
}
std::swap(data[i], data[end]);
return i;
}
void QuickSort(int* data, int length, int start, int end){
if (start == end)
return;
int pivotIdx = Partition(data, length, start, end);
if (pivotIdx > start)
QuickSort(data, length, start, pivotIdx - 1);
if (pivotIdx < end)
QuickSort(data, length, pivotIdx + 1, end);
}
void QuickSortPort(int* data, int length){
if (data == nullptr || length <= 0)
return;
QuickSort(data, length, 0, length - 1);
}
//数组中出现次数超过一次的数字：
// 第一种方法：转化为查找数组中位数的问题，但不一定需要排序，只要使用快速查找第k个元素即可,
// 缺点：会修改输入数组
#include <stdlib.h>
#include <time.h>
int randomInRange(int start, int end){
srand((unsigned int)(time(NULL)));
if (start == end)
return start;
else if (start > end)
return end + rand() % (start - end + 1);
else
return start + rand() % (end - start + 1);
}
bool g_bIalidInput = false;
int Partition(int* data, int length, int start, int end){
if (data == nullptr || length<= 0 || start < 0 || end > length - 1){
g_bInvalidInput = true;
return 0;
}
int pivotIdx = randomInRange(start, end);
int pivot = data[pivotIdx];
std::swap(data[pivotIdx], data[end]);
int i = start - 1;
int j = end;
while (i <= end - 1 && j >= start){
while (data[++i] < pivot) {;}
while (data[--j] > pivot) {;}
if (i < j)
std::swap(data[i], data[j]);
else
break;
}
std::swap(data[i], data[end]);
return i;
}
bool CheckMoreThanHalf(int* data, int length, int result){
bool isConfirmed = true;
int count = 0;
for (int i = 0; i < length; ++i){
if (data[i] == result)
count++;
}
if (count*2 <= length)
isConfirmed = false;
return isConfirmed;
}
int FindMoreThanHalf(int* data, int length){
if (data == nullptr || length <= 0){
g_bIalidInput = true;
return 0;
}
int start = 0;
int end = length - 1;
int pivotIdx = Partition(data, length, start, end);
int middle = length >> 1;
while (pivotIdx != middle){
if (pivotIdx < middle)
pivotIdx = Partition(data, length, pivotIdx + 1, end);
else
pivotIdx = Partition(data, length, start, pivotIdx - 1);
}
int result = data[pivotIdx];
if (CheckMoreThanHalf(data, length, result))
return result;
else {
g_bInvalidInput = true;
return 0;
}
}
//数组中出现次数超过一半的数字：
// 第二种方法：出现超过一半的数字出现总次数超过其他所有数字次数，无需修改数组
bool g_bInvalidInput = false;
bool CheckMoreThanHalf(int* data, int length, int result){
bool isConfirmed = true;
int count = 0;
for (int i = 0; i < length; ++i){
if (data[i] == result)
count++;
}
if (count*2 <= length)
isConfirmed = false;
return isConfirmed;
}
int FindMoreThanHalf2(int* data, int length){
if (data == nullptr || length <= 0){
g_bInvalidInput = true;
return 0;
}
int number = data[0];
int count = 1;
for (int i = 1; i < length; ++i){
if (data[i] == number)
count++;
else if (count != 0)
count--;
else {
number = data[i];
count = 1;
}
}
if (CheckMoreThanHalf(data, length, number))
return number;
else {
g_bInvalidInput = true;
return 0;
}
}
// 找出最小的k个数：不要求排序
// 第一种方法：快速查找O(n)时间复杂度，利用快速排序思想，Partition函数，
#include <stdlib.h>
#include <time.h>
int randomInRange(int start, int end){
srand((unsigned int)(time(NULL)));
if (start == end)
return start;
else if (start > end)
return end + rand() % (start - end + 1);
else
return start + rand() % (end - start + 1);
}
bool g_bInvalidInput = false;
int Partition(int* data, int length, int start, int end){
if (data == nullptr || length<= 0 || start < 0 || end > length - 1){
g_bInvalidInput = true;
return 0;
}
int pivotIdx = randomInRange(start, end);
int pivot = data[pivotIdx];
std::swap(data[pivotIdx], data[end]);
int i = start - 1;
int j = end;
while (i <= end - 1 && j >= start){
while (data[++i] < pivot) {;}
while (data[--j] > pivot) {;}
if (i < j)
std::swap(data[i], data[j]);
else
break;
}
std::swap(data[i], data[end]);
return i;
}
void leastKNumbers(int* data, int length, int k){
if (data == nullptr || length <= 0 || k <= 0 || k > length)
return;
int start = 0;
int end = length - 1;
int pivotIdx = Partition(data, length, start, end);
while (pivotIdx != k - 1){
if (pivotIdx > k - 1)
pivotIdx = Partition(data, length, start, pivotIdx - 1);
else
pivotIdx = Partition(data, length, pivotIdx + 1, end);
}
for (int i = 0; i <= pivotIdx; ++i){
if (i == pivotIdx)
cout << data[i] << endl;
else
cout << data[i] << ' ';
}
}
//第二种方法：利用二叉树（红黑树），STL中的set和multiset都是基于红黑树实现的最大/最小堆，支持O(log k)时间的插入c.insert(x)/删除操作c.erase(x), O(1)时间查找最大值c.begin()
//时间复杂度：nlogk，不会修改输入数据， 不要求一次载入所有数据到内存，只要求内存存储k个数字的一个容器，一次读入一个数据；
// 适合海量数据处理,即n很大， k很小的数据
#include <set>
#include <vector>
using namespace std;
typedef std::multiset<int, greater<int>> intSet;
typedef std::multiset<int, greater<int>>::iterator setIterator;
void leastKNumbers(const vector<int>& data, intSet& leastKNumbers, int k){
leastKNumbers.clear();
vector<int>::const_iterator iter = data.begin();
for (; iter != data.end(); ++iter){
if (leastKNumbers.size() < k){
leastKNumbers.insert(*iter);
}
else {
setIterator greatestIter = leastKNumbers.begin();
if ((*iter) < (*greatestIter)){
leastKNumbers.erase(greatestIter);
leastKNumbers.insert(*iter);
}
}
}
}
intSet leastKNumbersPort(const vector<int>& data, int k){
if (data.size() > 0 && k > 0 && k <= data.size()){
intSet leastKSet;
leastKNumbers(data, leastKSet, k);
return leastKSet;
}
else
throw exception();
}