java - 数组中的多数元素 (n/3)

Question

下面针对数组中大多数元素的代码适用于元素的n/2时间，但不适用于n/3时间。谁能帮我？

class Solution {
    public List<Integer> majorityElement(int[] a) {
        ArrayList<Integer> arr = new ArrayList<>();
        int flag=0;
        for (int i = 0; i < a.length; i++) {
            int count = 0;
            for (int j = i; j < a.length; j++) {
                if (a[i] == a[j])
                    count++;
            }
  
            if (count > a.length/3) {
                arr.add(a[i]);
                flag=1;
            }
        }
        if (flag==0)
            return new ArrayList<>();
        
        return arr;
    }
}

标签： javaarraysalgorithmdata-structures

Answer 1

您缺少所有那些索引低于i第二个 for 循环的元素。要计算一个数字的频率，您需要将它与数组中存在的所有元素等同起来，如果您以count = 0.
这是修改后的版本：

        ArrayList<Integer> arr = new ArrayList<>();
        for (int i = 0; i < a.length; i++)
        {
            int count = 0;
            for (int j = 0; j < a.length; j++)
                if (a[i] == a[j])
                    count++;
  
            if (count > a.length/3)
                arr.add(a[i]);
        }
        
        return arr;