Interview 150
Majority Element II
- Problem
- LC 229
- File
- interview150_LC229MajorityElementII.java
- Path
- pkg5leetcode/interview150/interview150_LC229MajorityElementII.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC229MajorityElementII.java
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/** LC 229 Majority Element II */4import java.util.*;5 6public class interview150_LC229MajorityElementII {7 static List<Integer> majorityElement(int[] nums) {8 int c1 = 0, c2 = 1, cnt1 = 0, cnt2 = 0;9 for (int x : nums) {10 if (x == c1) cnt1++; else if (x == c2) cnt2++;11 else if (cnt1 == 0) { c1 = x; cnt1 = 1; }12 else if (cnt2 == 0) { c2 = x; cnt2 = 1; }13 else { cnt1--; cnt2--; }14 }15 cnt1 = cnt2 = 0;16 for (int x : nums) { if (x == c1) cnt1++; else if (x == c2) cnt2++; }17 List<Integer> res = new ArrayList<>();18 int n = nums.length;19 if (cnt1 > n / 3) res.add(c1);20 if (c2 != c1 && cnt2 > n / 3) res.add(c2);21 return res;22 }23 24 public static void main(String[] args) {25 System.out.println(majorityElement(new int[]{3,2,3}));26 }27}