229 marjority element 2

2015-09-17 | 分类 leetcode | 标签 array

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

1

这道题很容易想到 marjority element 那道题。这类题称为Boyer-Moore Majority Vote Element Algorithm。我觉得和上一篇的一样，寻找大于n/2元素时，关键是从数组中去掉2个不同的元素，结论不变。寻找大于n/3元素时，关键是从数组中去掉3个不同的元素时，结论不变。

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
56
57 public List<Integer> majorityElement(int[] nums) {
        if(nums == null) return null;
        List<Integer> list = new ArrayList<Integer>();

    <span class="kt">int</span> <span class="n">candidate1</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
    <span class="kt">int</span> <span class="n">candidate2</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
    <span class="kt">int</span> <span class="n">count1</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
    <span class="kt">int</span>  <span class="n">count2</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
    <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">nums</span><span class="o">.</span><span class="na">length</span><span class="o">;</span> <span class="n">i</span><span class="o">++){</span>
        <span class="kt">int</span> <span class="n">tmp</span> <span class="o">=</span> <span class="n">nums</span><span class="o">[</span><span class="n">i</span><span class="o">];</span>

        <span class="k">if</span><span class="o">(</span><span class="n">count1</span> <span class="o">==</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">count2</span> <span class="o">==</span> <span class="mi">0</span><span class="o">){</span>
            <span class="n">candidate1</span> <span class="o">=</span> <span class="n">tmp</span><span class="o">;</span>
            <span class="n">count1</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span>
        <span class="o">}</span><span class="k">else</span> <span class="k">if</span><span class="o">(</span><span class="n">count1</span> <span class="o">==</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">count2</span> <span class="o">!=</span> <span class="mi">0</span><span class="o">){</span>
            <span class="k">if</span><span class="o">(</span><span class="n">tmp</span> <span class="o">!=</span> <span class="n">candidate2</span><span class="o">)</span> 
                <span class="o">{</span>
                    <span class="n">candidate1</span> <span class="o">=</span> <span class="n">tmp</span><span class="o">;</span>
                    <span class="n">count1</span><span class="o">++;</span>
                <span class="o">}</span>
            <span class="k">else</span> <span class="n">count2</span><span class="o">++;</span>
        <span class="o">}</span><span class="k">else</span> <span class="k">if</span><span class="o">(</span><span class="n">count2</span> <span class="o">==</span> <span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">count1</span> <span class="o">!=</span> <span class="mi">0</span><span class="o">){</span>
            <span class="k">if</span><span class="o">(</span><span class="n">tmp</span> <span class="o">!=</span> <span class="n">candidate1</span><span class="o">)</span> <span class="o">{</span>
                <span class="n">candidate2</span> <span class="o">=</span> <span class="n">tmp</span><span class="o">;</span>
                <span class="n">count2</span><span class="o">++;</span>
            <span class="o">}</span>
            <span class="k">else</span> <span class="n">count1</span><span class="o">++;</span>
        <span class="o">}</span><span class="k">else</span> <span class="k">if</span><span class="o">(</span><span class="n">tmp</span> <span class="o">==</span> <span class="n">candidate1</span><span class="o">){</span>
            <span class="n">count1</span><span class="o">++;</span>
        <span class="o">}</span><span class="k">else</span> <span class="k">if</span><span class="o">(</span><span class="n">tmp</span> <span class="o">==</span> <span class="n">candidate2</span><span class="o">){</span>
            <span class="n">count2</span><span class="o">++;</span>
        <span class="o">}</span><span class="k">else</span><span class="o">{</span>
            <span class="n">count1</span><span class="o">--;</span>
            <span class="n">count2</span><span class="o">--;</span>
        <span class="o">}</span>

    <span class="o">}</span>
    <span class="kt">int</span> <span class="n">count</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
    <span class="k">if</span><span class="o">(</span><span class="n">count1</span> <span class="o">!=</span> <span class="mi">0</span><span class="o">){</span>

        <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">nums</span><span class="o">.</span><span class="na">length</span><span class="o">;</span> <span class="n">i</span><span class="o">++){</span>
            <span class="k">if</span><span class="o">(</span><span class="n">candidate1</span> <span class="o">==</span> <span class="n">nums</span><span class="o">[</span><span class="n">i</span><span class="o">])</span> <span class="n">count</span><span class="o">++;</span>
        <span class="o">}</span>
        <span class="k">if</span><span class="o">(</span><span class="n">count</span> <span class="o">&gt;</span> <span class="n">nums</span><span class="o">.</span><span class="na">length</span><span class="o">/</span><span class="mi">3</span><span class="o">)</span>
            <span class="n">list</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="n">candidate1</span><span class="o">);</span>
    <span class="o">}</span>
    <span class="k">if</span><span class="o">(</span><span class="n">count2</span> <span class="o">!=</span> <span class="mi">0</span><span class="o">){</span>
        <span class="n">count</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
        <span class="k">for</span><span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">nums</span><span class="o">.</span><span class="na">length</span><span class="o">;</span> <span class="n">i</span><span class="o">++){</span>
            <span class="k">if</span><span class="o">(</span><span class="n">candidate2</span> <span class="o">==</span> <span class="n">nums</span><span class="o">[</span><span class="n">i</span><span class="o">])</span> <span class="n">count</span><span class="o">++;</span>
        <span class="o">}</span>
        <span class="k">if</span><span class="o">(</span><span class="n">count</span> <span class="o">&gt;</span> <span class="n">nums</span><span class="o">.</span><span class="na">length</span><span class="o">/</span><span class="mi">3</span><span class="o">)</span>
            <span class="n">list</span><span class="o">.</span><span class="na">add</span><span class="o">(</span><span class="n">candidate2</span><span class="o">);</span>
    <span class="o">}</span>
    <span class="k">return</span> <span class="n">list</span><span class="o">;</span>

<span class="o">}</span><span class="w">

代码写的罗嗦了一些，根据2中的python代码写了下面简洁一些的代码。仅是关键代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23      int candidate1 = 0;
        int candidate2 = 1;
        int count1 = 0;
        int  count2 = 0;
        for(int i = 0; i < nums.length; i++){
            int tmp = nums[i];

         <span class="k">if</span><span class="o">(</span><span class="n">tmp</span> <span class="o">==</span> <span class="n">candidate1</span><span class="o">){</span>
            <span class="n">count1</span><span class="o">++;</span>
        <span class="o">}</span><span class="k">else</span> <span class="k">if</span><span class="o">(</span><span class="n">tmp</span> <span class="o">==</span> <span class="n">candidate2</span><span class="o">){</span>
            <span class="n">count2</span><span class="o">++;</span>
        <span class="o">}</span><span class="k">else</span> <span class="k">if</span><span class="o">(</span><span class="n">count1</span> <span class="o">==</span> <span class="mi">0</span><span class="o">){</span>
                <span class="n">candidate1</span> <span class="o">=</span> <span class="n">tmp</span><span class="o">;</span>
                <span class="n">count1</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span>
        <span class="o">}</span><span class="k">else</span> <span class="k">if</span><span class="o">(</span><span class="n">count2</span> <span class="o">==</span> <span class="mi">0</span><span class="o">){</span>
                <span class="n">candidate2</span> <span class="o">=</span> <span class="n">tmp</span><span class="o">;</span>
                <span class="n">count2</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span>
        <span class="o">}</span><span class="k">else</span><span class="o">{</span>
            <span class="n">count1</span><span class="o">--;</span>
            <span class="n">count2</span><span class="o">--;</span>
        <span class="o">}</span>

    <span class="o">}</span><span class="w">

2 most votes

by chungyushao

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution:
# @param {integer[]} nums
# @return {integer[]}
def majorityElement(self, nums):
    if not nums:
        return []
    count1, count2, candidate1, candidate2 = 0, 0, 0, 1
    for n in nums:
        if n == candidate1:
            count1 += 1
        elif n == candidate2:
            count2 += 1
        elif count1 == 0:
            candidate1, count1 = n, 1
        elif count2 == 0:
            candidate2, count2 = n, 1
        else:
            count1, count2 = count1 - 1, count2 - 1
    return [n for n in (candidate1, candidate2)
                    if nums.count(n) > len(nums) // 3]