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

lo8azlld  于 2021-08-20  发布在  Java
关注(0)|答案(2)|浏览(326)

以下数组中多数元素的代码适用于 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;
    }
}
332nm8kg

332nm8kg1#

为了计算每个元素的频率,您需要从i=0到n和j=0到n进行遍历,如果您使用hashmap来解决它会更好,现在的时间复杂度是o(n2),使用hashmap您可以在o(n)中解决它
https://www.geeksforgeeks.org/majority-element/

hujrc8aj

hujrc8aj2#

您缺少索引低于的所有元素 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;

相关问题