//快速排序：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();

}

最新文章

1. iOS--UIAlertView与UIAlertController和UIAlertAction之间的事儿
2. Url获取图片流并打包~
3. BZOJ3669 （动态树）
4. 智能车学习（二十三）——浅谈心得体会
5. STL之map应用 +hash表（51nod 1095）
6. Oracle数据库多语言文字存储解决方案
7. bzoj3998 [TJOI2015]弦论（SAM）
8. parcel write boolean值
9. Codeforces 494B Obsessive String
10. 报表 jasper + ireport5.6
11. oracle如何导出和导入数据库表
12. Pycharm配置Git和Github
13. Django url
14. 2019.03.29 bzoj5463: [APIO2018] 铁人两项（圆方树+树形dp）
15. centos7 Mycat/MySQL/MariaDB安装部署
16. python字符串str和字节数组bytes相互转化
17. Linux下如何查看系统启动时间和运行时间(转)
18. Mybatis 系列6-结合源码解析节点配置：objectFactory、databaseIdProvider、plugins、mappers
19. 将数据导入MongoDB集群与MySQL
20. 一步一步pwn路由器之radare2使用实战

热门文章

1. redis 订阅与发布
2. 使用VMware安装CentOS
3. 统一代码风格工具——editorConfig
4. iOS源码博文集锦3
5. Kaggle竞赛 —— 泰坦尼克号（Titanic）
6. React Native 系列(六) -- PropTypes
7. mybatis 详解（七）------一对一、一对多、多对多
8. 2016 "Bird Cup" ICPC7th@ahstu--“波导杯”安徽科技学院第七届程序设计大赛
9. Linux Command Line(II): Intermediate
10. 13. Roman to Integer【leetcode】