码疯窝

LeetCode 每日一题 — Majority Element

2015/01/14 12:22:09    分类: 日志连载    0人评论 次浏览

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.

算法分析: 这道题目解法就多了, 下面就列举几种简单好用的解法.
思路一: 最笨的方法, 挨个检测此元素出现的次数, 时间复杂度O(n2)
思路二: 用hash table 记录每个元素出现的次数, 然后找出出现最多的那一个. 时间复杂度O(n), 空间复杂度O(n)
思路三: 先排序, 然后再取n/2的那个元素就是了, 时间复杂度由排序算法决定了. 时间复杂度O(nlogn)
思路四: 随机抽取一个元素, 然后判断他的出现次数是否是大天n/2, 因为随机抽取一个的话, 抽中的概率已经大于1/2了.最优时间复杂度为O(n)
思路五: 两个不同的数删除, 留到最后的就是我们要的结果. 或者些方法可以理解为投票, 先假设是第一个是的, 然后再遍历到他时就给他加一票, 否则减一票, 票数为0时换个元素. 时间复杂度 O(n)
等等等…

其中, 我java 是用的思路5, C++ 用思路四, Python 用思路三, 均通过leetcode.

Java:

public class Solution {
    public int majorityElement(int[] num) {
        int len = num.length;
        int times = 0;
        int v = 0;
        for (int i = 0; i < len; i ++) {
            if (times == 0)
                v = num[i];
            if (num[i] == v) {
                times++;
            } else {
                times--;
            }
        }
        return v;
    }
}

C++:

class Solution {
public:
    int majorityElement(vector &num) {
        int i = 0;
        int len = num.size();
        int v = 0;
        int j = 0;
        int times = 0;
        if (len == 1)
            return num[0];
        while(true) {
            v = num[rand() % (len - 1)];
            times = 0;
            for (j = 0; j < len; j++) {
                if (v == num[j])
                    times++;
            }
            if (times > len / 2)
                break;
        }
        return v;
    }
};

Python:

class Solution:
    # @param num, a list of integers
    # @return an integer
    def majorityElement(self, num):
        return sorted(num)[len(num) / 2]
继续查看有关 日志连载的文章

0个访客评论