|
Given an integer array of size n, find all elements that appear more than
? n/3 ? times. The algorithm should run in linear time and in O(1) space.import java.util.ArrayList; import java.util.List; public class Solution { public static List<Integer> majorityElement(int[] nums) { List<Integer> result=new ArrayList<Integer>(); int n = nums.length; int num1 = 0, num2=0; int counter1 = 0; int counter2 = 0; for (int i = 0; i < n; i++) { if (counter1 == 0 || num1 == nums[i]) { num1 = nums[i]; counter1++; } else if (counter2 == 0 || num2 == nums[i]) { num2 = nums[i]; counter2++; } else { counter1--; counter2--; } } counter1 = 0; counter2 = 0; for (int i = 0; i < n; i++) { if (nums[i] == num1) { counter1++; } else if (nums[i] == num2) { counter2++; } } if (counter1 > n/3) { result.add(num1); } if (counter2 > n/3) { result.add(num2); } return result; } public static void main(String args[]){ int[] a={1,2}; List<Integer> b=majorityElement(a) ; } } |
|
|
