Lintcode: Majority Number 解题报告

Majority Number

原题链接:http://lintcode.com/en/problem/majority-number/#

Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it.

Example

For [1, 1, 1, 1, 2, 2, 2], return 1

Challenge

O(n) time and O(1) space

SOLUTION 1:

http://www.geeksforgeeks.org/majority-element/

这里是一篇论文: http://www.cs.utexas.edu/~moore/best-ideas/mjrty/

这里用的算法是:MJRTY - A Fast Majority Vote Algorithm

1. 简单来讲,就是不断对某个议案投票,如果有人有别的议案,则将前面认为的议案的cnt减1,减到0换一个议案。

如果存在majority number,那么这个议案一定不会被减到0,最后会胜出。

2. 投票完成后,要对majority number进行检查,以排除不存在majority number的情况。如 1,2,3,4这样的数列,是没有majory number的。

很简单,统计一下结果议案的票数,没有过半就是没有majority number.

摘录一段解释:

METHOD 3 (Using Moore’s Voting Algorithm)

This is a two step process.
1. Get an element occurring most of the time in the array. This phase
will make sure that if there is a majority element then it will return
that only.
2. Check if the element obtained from above step is majority element.

1. Finding a Candidate:
The algorithm for first phase that works in O(n) is known as Moore’s
Voting Algorithm. Basic idea of the algorithm is if we cancel out each
occurrence of an element e with all the other elements that are
different from e then e will exist till end if it is a majority element.

findCandidate(a[], size)
1.  Initialize index and count of majority element
     maj_index = 0, count = 1
2.  Loop for i = 1 to size – 1
    (a)If a[maj_index] == a[i]
        count++
    (b)Else
        count--;
    (c)If count == 0
        maj_index = i;
        count = 1
3.  Return a[maj_index]

Above algorithm loops through each element and maintains a count of a[maj_index], If next element is same then increments the count, if next element is not same then decrements the count, and if the count reaches 0 then changes the maj_index to the current element and sets count to 1.
First Phase algorithm gives us a candidate element. In second phase we
need to check if the candidate is really a majority element. Second
phase is simple and can be easily done in O(n). We just need to check if
count of the candidate element is greater than n/2.

Example:
A[] = 2, 2, 3, 5, 2, 2, 6
Initialize:
maj_index = 0, count = 1 –> candidate ‘2?
2, 2, 3, 5, 2, 2, 6

Same as a[maj_index] => count = 2
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 1
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 0
Since count = 0, change candidate for majority element to 5 => maj_index = 3, count = 1
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 0
Since count = 0, change candidate for majority element to 2 => maj_index = 4
2, 2, 3, 5, 2, 2, 6

Same as a[maj_index] => count = 2
2, 2, 3, 5, 2, 2, 6

Different from a[maj_index] => count = 1

Finally candidate for majority element is 2.

First step uses Moore’s Voting Algorithm to get a candidate for majority element.

2. Check if the element obtained in step 1 is majority

printMajority (a[], size)
1.  Find the candidate for majority
2.  If candidate is majority. i.e., appears more than n/2 times.
       Print the candidate
3.  Else
       Print "NONE"

 1 package Algorithms.lintcode.math;
 2
 3 import java.util.ArrayList;
 4
 5 public class MajorityNumber {
 6     /**
 7      * @param nums: a list of integers
 8      * @return: find a  majority number
 9      */
10     public int majorityNumber(ArrayList<Integer> nums) {
11         // write your code
12         if (nums == null || nums.size() == 0) {
13             // No majority number.
14             return -1;
15         }
16
17         int candidate = nums.get(0);
18
19         // The phase 1: Voting.
20         int cnt = 1;
21         for (int i = 1; i < nums.size(); i++) {
22             if (nums.get(i) == candidate) {
23                 cnt++;
24             } else {
25                 cnt--;
26                 if (cnt == 0) {
27                     candidate = nums.get(i);
28                     cnt = 1;
29                 }
30             }
31         }
32
33         // The phase 2: Examing.
34         cnt = 0;
35         for (int i = 0; i < nums.size(); i++) {
36             if (nums.get(i) == candidate) {
37                 cnt++;
38             }
39         }
40
41         // No majory number.
42         if (cnt <= nums.size() / 2) {
43             return -1;
44         }
45
46         return candidate;
47     }
48 }

GITHUB:

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/lintcode/math/MajorityNumber.java

时间: 12-18

Lintcode: Majority Number 解题报告的相关文章

Lintcode: Majority Number II 解题报告

Majority Number II 原题链接: http://lintcode.com/en/problem/majority-number-ii/# Given an array of integers, the majority number is the number that occurs more than 1/3 of the size of the array. Find it. Note There is only one majority number in the arra

USACO Section1.2 Name That Number 解题报告

namenum解题报告 —— icedream61 博客园(转载请注明出处)------------------------------------------------------------------------------------------------------------------------------------------------[题目] 你有一个手机,键盘如下所示: 2: A,B,C 5: J,K,L 8: T,U,V 3: D,E,F 6: M,N,O 9:

[LintCode] Majority Number(以时间复杂度O(n)求主元素)

一个数据序列的主元素,是指序列中出现次数超过序列长度一半的元素. 法1(期望时间复杂度为O(n)): 由于主元素出现次数超过序列长度的一半,因此,主元素一定是中位数.可以利用递归划分求中位数的方法,期望时间复杂度为O(n). 法2: 显然,如果一个序列存在主元素,那么我们去掉序列中不同的两个数,剩下序列的主元素和原序列的主元素相同. 具体算法操作:记录两个量,当前元素x,计数cnt.初始化cnt为0:然后遍历序列,若cnt为0,则将x设为当前元素并将cnt置为1,否则,若当前元素和x相同,那么c

[LintCode] Majority Number 求众数

Given an array of integers, the majority number is the number that occurs more than half of the size of the array. Find it. Notice You may assume that the array is non-empty and the majority number always exist in the array. Have you met this questio

ACM Minimum Inversion Number 解题报告 -线段树

C - Minimum Inversion Number Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Description The inversion number of a given number sequence a1, a2, ..., an is the number of pairs (ai, aj) that satisfy i < j and ai > aj.

lintcode: k Sum 解题报告

k SumShow Result My Submissions http://www.lintcode.com/en/problem/k-sum/ 题目来自九章算法 13% Accepted Given n distinct positive integers, integer k (k <= n) and a number target. Find k numbers where sum is target. Calculate how many solutions there are? Ex

Lintcode: Fast Power 解题报告

Fast Power 原题链接:http://lintcode.com/en/problem/fast-power/# Calculate the an % b where a, b and n are all 32bit integers. Example For 231 % 3 = 2 For 1001000 % 1000 = 0 Challenge O(logn) Tags Expand SOLUTION 1: 实际上这题应该是suppose n > 0的. 我们利用 取模运算的乘法法则:

【原创】leetCodeOj --- Largest Number 解题报告

原题地址: https://oj.leetcode.com/problems/largest-number/ 题目内容: Given a list of non negative integers, arrange them such that they form the largest number. For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330. Note: The result may

[leetcode] 306. Additive Number 解题报告

题目链接: https://leetcode.com/problems/additive-number/ Additive number is a string whose digits can form additive sequence. A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the