169 marjority element

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

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.

1

我的思路是先排序，取中间元素，题目中说明了数组非空且肯定存在主元素，所以不用再验证了。

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 public int majorityElement(int[] nums) {
    quickSort(nums);
    return nums[nums.length / 2];
}
public void quickSort(int[] nums){
        if(nums == null || nums.length <  1) return;
        int hi = nums.length - 1;
        quickSort(nums,0,hi);

<span class="o">}</span>
<span class="kd">private</span> <span class="kt">void</span> <span class="nf">quickSort</span><span class="o">(</span><span class="kt">int</span><span class="o">[]</span> <span class="n">nums</span><span class="o">,</span> <span class="kt">int</span> <span class="n">lo</span><span class="o">,</span><span class="kt">int</span> <span class="n">hi</span><span class="o">){</span>
    <span class="k">if</span><span class="o">(</span><span class="n">lo</span> <span class="o">&gt;=</span> <span class="n">hi</span><span class="o">)</span> <span class="k">return</span><span class="o">;</span>
    <span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">partition</span><span class="o">(</span><span class="n">nums</span><span class="o">,</span><span class="n">lo</span><span class="o">,</span><span class="n">hi</span><span class="o">);</span>
    <span class="n">quickSort</span><span class="o">(</span><span class="n">nums</span><span class="o">,</span><span class="n">lo</span><span class="o">,</span><span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="o">);</span>
    <span class="n">quickSort</span><span class="o">(</span><span class="n">nums</span><span class="o">,</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="o">,</span><span class="n">hi</span><span class="o">);</span>
<span class="o">}</span>
<span class="kd">private</span> <span class="kt">int</span> <span class="nf">partition</span><span class="o">(</span><span class="kt">int</span><span class="o">[]</span> <span class="n">nums</span><span class="o">,</span><span class="kt">int</span> <span class="n">lo</span><span class="o">,</span><span class="kt">int</span> <span class="n">hi</span><span class="o">){</span>
    <span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">lo</span><span class="o">;</span>
    <span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">hi</span><span class="o">+</span><span class="mi">1</span><span class="o">;</span>
    <span class="kt">int</span> <span class="n">v</span> <span class="o">=</span> <span class="n">nums</span><span class="o">[</span><span class="n">lo</span><span class="o">];</span>
    <span class="k">while</span><span class="o">(</span><span class="kc">true</span><span class="o">){</span>
        <span class="k">while</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="o">&lt;</span> <span class="n">v</span><span class="o">)</span> <span class="k">if</span><span class="o">(</span><span class="n">i</span> <span class="o">==</span> <span class="n">hi</span><span class="o">)</span> <span class="k">break</span><span class="o">;</span>
        <span class="k">while</span><span class="o">(</span><span class="n">v</span> <span class="o">&lt;</span> <span class="n">nums</span><span class="o">[--</span><span class="n">j</span><span class="o">])</span> <span class="k">if</span><span class="o">(</span><span class="n">j</span> <span class="o">==</span> <span class="n">lo</span><span class="o">)</span> <span class="k">break</span><span class="o">;</span>
        <span class="k">if</span><span class="o">(</span><span class="n">i</span> <span class="o">&gt;=</span> <span class="n">j</span><span class="o">)</span> <span class="k">break</span><span class="o">;</span>
        <span class="n">swap</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">j</span><span class="o">);</span>
    <span class="o">}</span>
    <span class="n">swap</span><span class="o">(</span><span class="n">nums</span><span class="o">,</span><span class="n">lo</span><span class="o">,</span><span class="n">j</span><span class="o">);</span>
    <span class="k">return</span> <span class="n">j</span><span class="o">;</span>
<span class="o">}</span>
 <span class="kd">private</span> <span class="kt">void</span> <span class="nf">swap</span><span class="o">(</span><span class="kt">int</span><span class="o">[]</span> <span class="n">nums</span><span class="o">,</span><span class="kt">int</span> <span class="n">i</span><span class="o">,</span> <span class="kt">int</span> <span class="n">j</span><span class="o">){</span>
        <span class="k">if</span><span class="o">(</span><span class="n">i</span> <span class="o">==</span> <span class="n">j</span><span class="o">)</span> <span class="k">return</span><span class="o">;</span>
        <span class="k">if</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="o">==</span> <span class="n">nums</span><span class="o">[</span><span class="n">j</span><span class="o">])</span> <span class="k">return</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="o">^=</span> <span class="n">nums</span><span class="o">[</span><span class="n">j</span><span class="o">];</span>
        <span class="n">nums</span><span class="o">[</span><span class="n">j</span><span class="o">]</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">nums</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">^=</span> <span class="n">nums</span><span class="o">[</span><span class="n">j</span><span class="o">];</span>
    <span class="o">}</span><span class="w">

2 most votes

《编程之美》2.3寻找发帖水王中提到这个算法的解法:

如果每次删除两个不同的ID，那么在剩下的ID列表中，水王ID出现次数依然超过了一半。将问题转化为更小的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 public int majorityElement(int[] nums) {
        if(nums.length <= 1) return nums[0];
        int n = nums.length;
        int candidate = 0;
        int count = 0;
        for(int i = 0; i < n; i++){
            if(count == 0 ){
                candidate = nums[i];
                count = 1;
            }else{
                if(candidate == nums[i]) count++;
                else count--;
            }
        }
        return candidate;

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