Commitc3d3fb0

applewjg

committed

Majority Element

Change-Id: I01e7966c5fa16c6b3679e876f3f2a1bdaf0fb46f

1 parent1a5bc70 commitc3d3fb0Copy full SHA for c3d3fb0

File tree

+34

-0

lines changed

+34

-0

lines changed

Lines changed: 34 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,34 @@`
	`1`	`+/*`
	`2`	`+ Author: King, wangjingui@outlook.com`
	`3`	`+ Date: Dec 14, 2014`
	`4`	`+ Problem: ZigZag Conversion`
	`5`	`+ Difficulty: Easy`
	`6`	`+ Source: https://oj.leetcode.com/problems/majority-element/`
	`7`	`+ Notes:`
	`8`	`+ Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.`
	`9`	`+`
	`10`	`+ You may assume that the array is non-empty and the majority element always exist in the array.`
	`11`	`+`
	`12`	`+ Solution: Runtime: O(n) — Moore voting algorithm: We maintain a current candidate and a counter initialized to 0. As we iterate the array, we look at the current element x:`
	`13`	`+ If the counter is 0, we set the current candidate to x and the counter to 1.`
	`14`	`+ If the counter is not 0, we increment or decrement the counter based on whether x is the current candidate.`
	`15`	`+ After one pass, the current candidate is the majority element. Runtime complexity = O(n).`
	`16`	`+ */`
	`17`	`+publicclassSolution {`
	`18`	`+publicintmajorityElement(int[]num) {`
	`19`	`+intn =num.length;`
	`20`	`+if (n ==0)return0;`
	`21`	`+if (n ==1)returnnum[0];`
	`22`	`+intcur =num[0],cnt =1;`
	`23`	`+for (inti =1;i <n; ++i) {`
	`24`	`+if (cnt ==0) {`
	`25`	`+cur =num[i];`
	`26`	`+ ++cnt;`
	`27`	`+continue;`
	`28`	`+ }`
	`29`	`+if (cur ==num[i]) ++cnt;`
	`30`	`+else --cnt;`
	`31`	`+ }`
	`32`	`+returncur;`
	`33`	`+ }`
	`34`	`+}`

Comments

(0)