java - 我怎样才能加快我的多数元素问题集的以下算法？

Question

因此，我必须为我在 Coursera 中的数据结构作业编写一个算法。我已将 Java 用于以下问题集。

问题:- 那么，让我们考虑一个包含 5 个元素的数组中的数字序列。元素数量 - 5数组元素 - 2, 2 3, 9, 2

• 多数元素算法指出，如果一个元素出现超过 n/2 次，那么它就是数组中的多数元素。因此，我的程序应该输出 1(表示找到多数元素)、0(没有找到多数元素)。

根据上述问题- 2 在数组中出现 3 次，这意味着 n/2 次(5/2 = 2(整数，忽略小数)+ 1 = 3)

因此，我被要求编写一个算法来解决这个问题。选项是分而治之(即将数组分成两半并在两半中寻找多数元素然后得到答案)另一种选择是使用两个 for 循环扫描数组中的元素并最终获得多数元素。这是我试过的。我跑过评分机，但我的程序超出了时间限制。任何人都可以提出任何建议。谢谢!

Java 代码:-

import java.util.*;

import java.io.*;

public class MajorityElement {
    private static int getMajorityElement(int[] a, int left, int right) {

        int  count = 1;

        int num = a.length/2 + 1;
        Arrays.sort(a);
        if (left == right) {
            return -1;
        }
        if (left + 1 == right) {
            return a[left];
        }

        else
        {



            for(int i=0;i<a.length;i++)
            {
                for(int j=i+1;j<a.length;j++)
                {
                    if(a[i]==a[j])
                    {
                        count++;

                    }
                }

                if(count>1)
                {

                    if(count>=num)
                    {
                        return 1;

                    }
                    i = i + count-1;
                    count = 1;
                }

            }
            return -1;
        }
    }

    public static void main(String[] args) {
        FastScanner scanner = new FastScanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        if (getMajorityElement(a, 0, a.length) != -1) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }

    }
    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        FastScanner(InputStream stream) {
            try {
                br = new BufferedReader(new InputStreamReader(stream));
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

Answer 1

两个 for 循环方法只是是这样的:

for (int x: a) {
    int count = 0;
    for (int y: a) {
        if (x == y) {
            count++;
            if (count > a.length/2) {
                return true;
            }
         }
    }
}
return false;

在没有多数元素的情况下，这肯定会花费太长时间，因为它需要进行 n^2 次比较，其中 n 是列表中元素的数量。不要那样做。你可以先排序，就像你的问题的评论者说的那样，这会让你早点突破，但你仍然有排序的开销，然后是一些扫描。这看起来像(未测试，因为它是给你写的):

Arrays.sort(a); // actually I hate this because it mutates your array (BAD!)
for (int i = 0; i < a.length; i++) {
    int count = 0;
    for (int j = i; i < j.length; j++) {
        if (a[j] == a[i]) {
            count++;
            if (count > a.length / 2) {
                return true;
            }
         } else if (a[j] > a[i]) {
             break; // no more to count
         }
    }
}
return false;

您可能想要采用分而治之的方法 (n log n)。还有 O(n) 算法，包括 J. Moore 的算法，它是这样的:

count = 0
for (int x: a) {
    if (count == 0) {
        candidate = x;
    }
    if (x == candidate) {
        count += 1
    } else {
        count -= 1
    }
}
count = 0;
for (int x: a) if (a==candidate) count++;
return count > a.length / 2;

将以上内容视为伪代码，因为它未经测试。

关于众数元素的更多信息 here但它全部在 Python 中，所以它可能无济于事。