算法设计与分析[0001] Divide and Conquer

编程珠玑Algorithm

　本周的 part 是 Divide and Conquer（分而治之）。

169. Majority Element

  • Level: Easy
  • Description

    　Given an array of size n, find the majority element. The majority element is the element that appears more than $⌊ n/2 ⌋$ times.
    　You may assume that the array is non-empty and the majority element always exist in the array.

  • 解题思路
    • Majority Element: A majority element in an array A[] of size n is an element that appears more than n/2 times（显然，只有唯一一个）
    • 可以通过构造 size 为 n 的向量表计数每个数字出现的次数（$O(n)$ 线性时间复杂度），在计数过程中，一旦发现 $count > n/2$ 即可返回，该数字即为要找的 Majority Element
    • 细想发现，使用数组构建的向量表，通过下标直接访问的方式，必须满足一个前提条件：n 个元素必须 $\in [0, n)$，所以感觉需要维护两个 size 为 n 的数组，一个保存出现的数字 $elements[0…n)$，另一个是对应的计数 $count[0…n)$，但是这样问题就出现了：在一遍遍历计数每个数字出现的次数过程中，为了找到对应的 $count[0…n)$ 下标，需要对 $elements[0…n)$ 进行查找
    • 考虑了以上的情况，决定使用 C++ 中的 map 字典来实现上述的想法，避免手动维护这样一个字典功能带来的低效率和繁琐工作量（毕竟是 Easy）
  • Solution & Analysis
    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:
        int majorityElement(vector<int>& nums) {
            if(1 == nums.size()) {
                return nums[0];
            }
            map<int, int> table;
            map<int, int>::iterator table_iter = table.end();
     
            for(vector<int>::iterator iter=nums.begin(); iter!=nums.end(); iter++){
                if(table.end() == table.find(*iter)){
                    table.insert(pair<int,int>(*iter, 1));
                }
                else{
                    table[*iter]++;
                    if(table[*iter] > nums.size()/2){
                        return (*iter);
                    }
                }
     
            }
            return -1;
        }
    };

　Accepted，不过耗时：38ms，应该有更高效的方式。

  • 补充
    • 有一种算法：A Linear Time Majority Vote Algorithm ，其思路如下
      1. Initialize index and count of majority element: majorityElement = 0, count = 0
      2. Loop for n = 0 to size – 1
        　(c)If count == 0
        　　majorityElement = a[n]
        　　count = 1
        　(b)If majorityElement == a[n]
        　　count++
        　(b)Else
        　　count–;
      3. Return majorityElement
    • 代码实现如下，其时间复杂度只有：13 ms，大大降低了
      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
      int majorityElement(int* nums, int numsSize) {
          int count = 0, n, majorityElement;
          for (n = 0; n < numsSize; n++) {
        if (count == 0){
            majorityElement = nums[n];
        }
        if (nums[n] == majorityElement) {
            count++;
        }
        else {
            count--;
        }
          }
          count = 0;
          for (n = 0; n < numsSize; n++){
        if (nums[n] == majorityElement) {
            count++;
        }
          }
          if (count > numsSize/2){
        return majorityElement;
          }
           
          return -1;
      }

+

本文标题:算法设计与分析[0001] Divide and Conquer

文章作者:Gary

发布时间:2017-02-26, 14:00:22

最后更新:2020-03-28, 12:37:22

原始链接:http://durant35.github.io/2017/02/26/Algorithms_Divide and Conquer/

文章目录
  1. 1. 169. Majority Element