主元素

  |   分类   |   热度 ℃

前言

LintCode 是专注代码面试的在线评测系统，有很多代码题，可以用 Java、C++、Python 在线答题，我觉得还不错，就决定把做一做这些题，然后把题目的实现、优化思路写下来，一来是为了有更深的理解，二来是讨论一下还有没有更好的方法。

问题

LintCode：主元素

描述

给定一个整型数组，找出主元素，它在数组中的出现次数严格大于数组元素个数的二分之一。

样例

给出数组 [1,1,1,1,2,2,2] ，返回 1

挑战

要求时间复杂度为O(n)，空间复杂度为O(1)

实现

这个问题非常简单，不过完成挑战还是需要一个很讨巧的思想，先说一说正常的思路。

排序计数

问题分析

首先想到的是用一个合适的 Tuple 来分别存储每个值的个数，最后取最大的（因为题目默认是有主元素的）。然而这完全是人脑的思路，并不是适合计算机，而且从空间复杂度上就和过挑战无缘了。还是决定先进行排序，再遍历一遍，重复的就计数，大于一半就跳出、返回。

代码实现 - C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int majorityNumber(vector<int> nums) {
        sort(nums.begin(), nums.end());
        int len = nums.size();
        int count = 1;
        for(int i = 1; i < len; ++i)
            if(nums[i] == nums[i - 1]){
                count++;
                if(count * 2 > len)
                    return nums[i];
            }else
                count = 1;
        return 0;
    }
};

结果分析

  • 结果：23ms 通过测试，速度还不错。
  • 分析：由于排序，时间复杂度一定大于 $o(n)$ ，大概为 $o(nlog_2 n)$，不能完成挑战要求。空间复杂度由于快排占空间复杂度为 $o(1)$，遍历时变量为常数，所以整体空间复杂度为 $o(1)$ ， 符合挑战要求。

剪裁数组

问题分析

这并不是我想出来的方法，不过这个方法很是巧妙，所以在此记录并拿出来分享一下。核心的思路在于 当一个数组去掉两个不同的元素时，其主元素不改变 。

两个不相等的元素只有两种可能，两种情况分别为 去掉两个非主元素 和 去掉一个主元素和一个非主元素，无论如何主元素比例都不小于去掉之前。

所以从头开始遍历，只要凑成 n 对不相等元素就可以裁剪掉前面的部分。

代码实现 - C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int majorityNumber(vector<int> nums) {
        int len = nums.size();
        int count = 0;
        int majority;
        for(int i = 0; i < len; ++i){
            if(count == 0) majority = nums[i];
            if(majority == nums[i]) ++count;
            else --count;
        }
        return majority;
    }
};

结果分析

结果：21ms 通过测试，由于测试数据不大，速度提升并不是很明显。
分析：只遍历一次，时间复杂度 $o(n)$，常数个变量，空间复杂度 $o(1)$，虽然速度提升不明显，但是理论上通过挑战。

总结

简单题想做出花来也并非易事，每道题都有每道题的特点，生搬硬套、死记硬背可以解决很多问题但未必能完美解决。灵活来源于量的积累，多做题，多思考。


本文链接：主元素
版权声明：本文章采用CC BY-NC-SA 3.0 CN许可协议进行许可。转载请注明出处！