问题描述

给一个很多数(含重复元素)的集合，如何快速的对集合进行汇总，找出每个元素对应的个数？

思路

存放集合的数据结构，两种，一种使用 红黑树，一种使用 散列表。

  • 红黑树：插入时间为 o(nlogn)，查找时间为 O(nlogn)。
  • 散列表：理论插入时间为 O(1)，查找时间为 O(1)。实际上有可能出现 O(N^2)。另外，使用散列表的方式存放数据，需要使用大量的存储空间。

首先对集合进行排序，然后通过两个标识进行元素的计数。

从排完序的集合的首部元素开始，设置两个标识 L、R 在相同元素的边界处。开始时，L = R = 0，遍历排序后的集合元素，R++。当出现两个标识的元素不同时，令 L = R，同时统计改元素的个数为 R - L。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include <iostream>
#include <array>
#include <algorithm>

#include "DeleteRepeatElem.h"

void DelRepeatElems() {
    std::array<int, 15> elemArr{1, 2, 3, 4, 5, 6, 7, 342, 432, 43, 2, 34, 5, 6, 2};
    std::sort(elemArr.begin(), elemArr.end());

    int L = 0, R = 0;
    for (; R < elemArr.size(); ++R) {
        if (elemArr[L] != elemArr[R]) {
            std::cout << elemArr[L] << " number is " << R - L << std::endl;
            L = R;
        }
    }
    std::cout << elemArr[L] << " number is " << R - L << std::endl;
}

关键思想是，先排序，再找重复的元素。时间复杂度方面，使用内置的排序算法，复杂度为 O(nlogn)，找出重复次数的话，时间复杂度为 O(n)。所以，整体的时间复杂度为 O(nlogn)。

Leetcode

关于这部分的leetcode题目有一些。