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.
方法很笨，其实时间复杂度差不多是O(n²)。
package leetcode;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
//import java.util.Scanner;
import java.util.Set;
public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> result = new ArrayList<Integer>();
int n = nums.length;
int m = n/3;
Set<Integer> myset= new HashSet<Integer>();
for(int i=0;i<n;i++)
{
myset.add(nums[i]);
}
Iterator<Integer> iterator = myset.iterator();
while(iterator.hasNext())
{
int thisnum = iterator.next();
int count = 0;
for(int i=0;i<n;i++)
{ if(thisnum == nums[i])
{
count++;
if(count>m)
{
result.add(thisnum);
break;
}
}
}
}
return result; }
public static void main(String[] args)
{
Solution sl = new Solution();
int[] nums = {2,2,4,6,7,4,2,4};
List<Integer> result = sl.majorityElement(nums);
System.out.println(result); }
}