majority_element_II

hitzzc · hitzzc · commit c83db7400779 · 2016-10-17T23:55:39.000+08:00
diff --git a/README.md b/README.md
@@ -185,6 +185,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [226. Invert Binary Tree](https://github.com/hitzzc/go-leetcode/tree/master/invert_binary_tree)
 #### [227. Basic Calculator II](https://github.com/hitzzc/go-leetcode/tree/master/basic_calculator_II)
 #### [228. Summary Ranges](https://github.com/hitzzc/go-leetcode/tree/master/summary_ranges)
+#### [229. Majority Element II](https://github.com/hitzzc/go-leetcode/tree/master/majority_element_II)
 
 
 
diff --git a/majority_element_II/majority_element_II.go b/majority_element_II/majority_element_II.go
@@ -0,0 +1,37 @@
+package majority_element_II
+
+func majorityElement(nums []int) []int {
+	var m, n, cm, cn int
+	for i := range nums {
+		if nums[i] == m {
+			cm++
+		} else if nums[i] == n {
+			cn++
+		} else if cm == 0 {
+			m = nums[i]
+			cm++
+		} else if cn == 0 {
+			n = nums[i]
+			cn++
+		} else {
+			cm--
+			cn--
+		}
+	}
+	cm, cn = 0, 0
+	for i := range nums {
+		if nums[i] == m {
+			cm++
+		} else if nums[i] == n {
+			cn++
+		}
+	}
+	var ret []int
+	if cm > len(nums)/3 {
+		ret = append(ret, m)
+	}
+	if cn > len(nums)/3 {
+		ret = append(ret, n)
+	}
+	return ret
+}
