算法基础算法

非比较排序

字数统计: 2.4k字   |   阅读时长: 12分
, ,

$1.1 计数排序

当数据范围较小，例如十万级，可以通过一个计数数组统计各个数字出现的次数，然后在按照出现的数字和次数从小到大依次写回原数组

使用场景:

  • 数据范围说明用计数排序
  • 某些数据结构的操作也基于计数排序，例如后缀数组。

整个流程是先计数，再统计。统计阶段有种实现方式，一种不稳定但是好写，另一种稳定但是不好写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 计数排序,
// 1 <= A.length <= 10000
// -50000 <= A[i] <= 50000
void countingsort(vector<int>& nums)
{
    if(nums.empty()) return;
    int n = nums.size();
    if(n == 1) return;
    // 范围 [-50000, 50000] 映射到[0, 100000]
    for(int i = 0; i < n; ++i)
        nums[i] += 50000;
    int m = 100001; //[0, 100000]
    // _countingsort1(nums, m);
    _countingsort2(nums, m);
    for(int i = 0; i < n; ++i) // 减回来
        nums[i] -= 50000;
}

  • 不保证稳定, 也叫假计数排序

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    void _countingsort1(vector<int>& nums, int m)
    {
        int n = nums.size();
        vector<int> cnt(m + 1, 0);
        for(int i = 0; i < n; ++i) cnt[nums[i]]++;

        for(int i = 0, k = 0; i <= m; ++i)
        {
            while(cnt[i]){
                nums[k++] = i;
                cnt[i]--;
            }
        }
    }

  • 保证稳定, 借助 cnt 数组的前缀和

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    void _countingsort2(vector<int>& nums, int m)
    {
        int n = nums.size();
        vector<int> cnt(m + 1, 0);
        for(int i = 0; i < n; ++i) cnt[nums[i]]++;

        vector<int> presum_cnt(m + 2, 0);
        for(int i = 1; i < m + 2; ++i)
            presum_cnt[i] = presum_cnt[i - 1] + cnt[i - 1];
        vector<int> tmp(nums.begin(), nums.end()); // nums 的副本

        for(int i = n - 1; i >= 0; --i)
            nums[--presum_cnt[tmp[i]]] = tmp[i];
    }

75. 颜色分类

三色排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    void sortColors(vector<int>& nums) {
        _countingsort(nums);
    }

private:
    // 基本计数排序
    void _countingsort(vector<int>& nums)
    {
        if(nums.empty()) return;
        int n = nums.size();
        if(n == 1) return;

        // 数据范围 0-2
        // 计数排序空间复杂度 O(N + K), K = 3
        int K = 3;
        vector<int> cnt(K, 0);
        for(int i = 0; i < n; ++i)
            ++cnt[nums[i]];

        for(int i = 0, k = 0; i < K; ++i)
            while(cnt[i] > 0)
            {
                nums[k++] = i;
                --cnt[i];
            }
    }
};

另解：双指针, 类似单指针 partition 的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    void sortColors(vector<int>& nums) {
        _twopointers(nums);
    }

private:
    // 双指针
    // 类似单指针 partition 的操作
    void _twopointers(vector<int>& nums)
    {
        if(nums.empty()) return;
        int n = nums.size();
        if(n == 1) return;

        int left = 0, right = n - 1; // n >= 2, right >= 1
        // left 的左侧都是 0, right 的右侧都是 2
        for(int i = 0; i <= right;)
        {
            if(nums[i] == 0)
                swap(nums[i++], nums[left++]);
            else if(nums[i] == 2)
                swap(nums[i], nums[right--]);
            else
                ++i;
        }
    }
};

280. 摆动排序

与计数排序无关，324. 摆动排序 II 的铺垫。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        if(nums.empty()) return;
        int n = nums.size();
        if(n == 1) return;

        // n >= 2
        for(int i = 1; i < n; ++i)
        {
            // if(i % 2 == 1 && nums[i] < nums[i - 1])
            //    swap(nums[i], nums[i - 1]);
            // if(i % 2 == 0 && nums[i] > nums[i - 1])
            //    swap(nums[i], nums[i - 1]);

            // 简化写法
            if ((i % 2 == 0) == (nums[i] > nums[i + 1]))
                swap(nums[i], nums[i - 1]);
        }
    }
};

324. 摆动排序 II

将 280. 摆动排序 中的小于等于改成严格小于，大于等于改成严格大于。其它条件不变。

三色排序是其中一步：上坡，下坡，平原可以视为三种颜色

力扣324-摆动排序II,三色排序应用

274. H 指数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int hIndex(vector<int>& citations) {
        if(citations.empty()) return 0;
        int n = citations.size();
        vector<int> cnt(n + 1, 0);
        for(int i: citations)
            ++cnt[min(i, n)];
        int k = n;
        for(int s = cnt[n]; k > s; s += cnt[k])
            --k;
        return k;
    }
};

945. 使数组唯一的最小增量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    int minIncrementForUnique(vector<int>& A) {
        int n = A.size();
        if(n < 2) return 0;
        int M = 40000;
        _countingsort(A, M);
        int cur = A[0];
        int res = 0;
        for(int i = 1; i < n; ++i)
        {
            if(A[i] > cur)
                cur = A[i];
            else
            {
                res += cur - A[i] + 1;
                ++cur;
            }
        }
        return res;
    }

private:
    void _countingsort(vector<int>& A, int M)
    {
        vector<int> cnt(M, 0);
        for(int num: A) ++cnt[num];
        int n = A.size();
        int j = 0;
        for(int i = 0; i < (int)cnt.size(); ++i)
        {
            int k = cnt[i];
            while(k > 0)
            {
                A[j] = i;
                ++j;
                --k;
            }
            if(j == n) break;
        }
    }
};

1122. 数组的相对排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        vector<bool> in_arr2(1001, false);
        for(int num: arr2)
            in_arr2[num] = true;
        vector<int> cnt(1001, 0);
        for(int num: arr1)
            ++cnt[num];
        vector<int> result;
        for(int num: arr2)
        {
            if(cnt[num] > 0)
            {
                for(int i = 0; i < cnt[num]; ++i)
                    result.push_back(num);
            }
        }
        for(int num = 0; num <= 1000; ++num)
        {
            if(in_arr2[num]) continue;
            if(cnt[num] == 0) continue;
            for(int i = 0; i < cnt[num]; ++i)
                result.push_back(num);
        }
        return result;
    }
};

$1.2 桶排序

把数据范围通过一个映射函数分为若干个桶，假定各个桶里的数据量是均匀的。且要保证桶间有序

当数据范围很大，例如20亿以上时，计数排序就不行了。但是可以分成1000个桶，桶的数据范围: 第一个桶 [0, 199999] 以此类推。每个桶的期望元素个数为 $n/1000$。这里有个关键假设: 每个桶里的元素个数比较平均。

桶内的排序可以使用任意一种排序，也可以继续使用桶排序。

映射函数要保证桶间的顺序，桶内可以是无序的。

极端情况每个数都是 1 个桶就是计数排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 桶排序
// 范围 [-50000, 50000] 映射到[0, 100000]
void bucketsort(vector<int>& nums)
{
    if(nums.empty()) return;
    int n = nums.size();
    if(n == 1) return;
    int m = 11; // m 个桶, 每个桶里 100000/m 个数, 100000 单独是一个桶
    _bucketsort2(nums, m);
}

// 用 vector 指针的 vector 存桶
void _bucketsort(vector<int>& nums, int m)
{
    // 数字 num -> 桶编号 i
    // (num + 50000) / 1000
    vector<vector<int>* > buckets(m, nullptr);
    for(int i = 0; i < m; ++i)
        buckets[i] = new vector<int>();

    int n = nums.size();
    for(int i = 0; i < n; ++i)
        buckets[(nums[i] + 50000) / (100000 / (m - 1))] -> push_back(nums[i]);

    for(int i = 0; i < m; ++i)
        quicksort(*(buckets[i]));

    int iter = 0;
    for(vector<int> *bucket: buckets)
        for(int num: *bucket)
            nums[iter++] = num;

    for(int i = 0; i < m; ++i)
        delete buckets[i];
}

// 用vector的vector 存桶
void _bucketsort2(vector<int>& nums, int m)
{
    // 数字 num -> 桶编号 i
    // (num + 50000) / 1000
    vector<vector<int> > buckets(m);

    int n = nums.size();
    for(int i = 0; i < n; ++i)
        buckets[(nums[i] + 50000) / (100000 / (m - 1))].push_back(nums[i]);

    for(int i = 0; i < m; ++i)
        quicksort(buckets[i]);

    int iter = 0;
    for(vector<int> bucket: buckets)
        for(int num: bucket)
            nums[iter++] = num;
}

164. 最大间距

力扣164-桶排序

347. 前 K 个高频元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> mapping; // num -> cnt
        for(int num: nums)
            ++mapping[num];
        int n = nums.size();
        vector<vector<int> > buckets(n + 1, vector<int>());
        for(auto it = mapping.begin(); it != mapping.end(); ++it)
            buckets[it -> second].push_back(it -> first);
        vector<int> result;
        for(int i = n; i >= 1 && k > 0; --i)
        {
            int cur_cnt = buckets[i].size();
            if(cur_cnt > 0)
                result.insert(result.end(), buckets[i].begin(), buckets[i].end());
            k -= cur_cnt;
        }
        return result;
    }
};

451. 根据字符出现频率排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string frequencySort(string s) {
        int n = s.size();
        if(n <= 2) return s;
        unordered_map<char, int> char_cnt;
        for(char c: s)
            ++char_cnt[c];
        vector<vector<char> > buckets(n + 1, vector<char>());
        for(auto it = char_cnt.begin(); it != char_cnt.end(); ++it)
            buckets[it -> second].push_back(it -> first);
        string result;
        for(int i = n; i >= 1; --i)
            if(!buckets[i].empty())
            {
                for(char c: buckets[i])
                {
                    string item(i, c);
                    result.insert(result.end(), item.begin(), item.end());
                }
            }
        return result;
    }
};

1424. 对角线遍历 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
        int n = nums.size();
        vector<vector<int>> buckets;
        int all = 0;
        for(int i = 0; i < n; ++i)
        {
            int m = nums[i].size();
            all += m;
            for(int j = 0; j < m; ++j)
            {
                int k = i + j;
                if((int)buckets.size() < k + 1)
                    buckets.push_back({});
                buckets[k].push_back(nums[i][j]);
            }
        }
        vector<int> result(all);
        int idx = 0;
        int N = buckets.size();
        for(int k = 0; k < N; ++k)
        {
            int bn = buckets[k].size();
            for(int i = bn - 1; i >= 0; --i)
                result[idx++] = buckets[k][i];
        }
        return result;
    }
};

$1.3 基数数排序

按照数位进行映射的桶排序，0~9 一共10个桶。int 范围 正负 20 亿，先按个位排，再按十位排，…，最多有10个数位，所以最多要做10次桶排序

有大量的取模和除法运算，使得 $O(N)$ 的常数很高，一般跑不过一般的 $O(N\log N)$ 算法，较少用到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 基数排序, 只能对正数用(以下代码用在含负数的数组报错)
// 且O(N)的常数较大，实际比 $O(N\log N)$ 慢, 很少用
void radixsort(vector<int>& nums)
{
    if(nums.empty()) return;
    int n = nums.size();
    if(n == 1) return;

    for(int i = 0; i < n; ++i)
        nums[i] += 50000;
    _radixsort(nums);
    for(int i = 0; i < n; ++i) // 减回来
        nums[i] -= 50000;

}

void _radixsort(vector<int>& nums)
{
    int n = nums.size();
    // 定义桶
    vector<vector<int> > cnt(10); // 数位一共有 10 种, 10 个桶
    for(int i = 0; i < 10; ++i)
    {
        for(int j = 0; j < 10; ++j) cnt[j].clear();

        for(int j = 0; j < n; ++j)
            cnt[get(nums[j], i)].push_back(nums[j]);

        for(int j = 0, k = 0; j < 10; ++j)
            for(int num: cnt[j])
                nums[k++] = num;
    }

}

int get(int x, int i) // 返回 x 的第 i 位
{
    while(i--) x /= 10;
    return x % 10;
}
Share