java - 计算数组中可被给定查询 k 整除的整数个数

Question

在这个问题中，我有一些查询，我必须输出 array 中 integers 的计数，它可以被 k(其中一个查询)整除.array 包含重复的元素。我正在尝试优化问题，我的方法如下:

代码:

public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
     int[] ar={2,4,6,9,11,34,654,23,32,54,76,21432,32543,435,43543,643,2646,4567,457654,75,754,7,567865,8765877,53,2};
     int query=sc.nextInt();
     int length=ar.length;
     int count=0;
     for (int i=0;i<query ;i++ ) {
        int x=sc.nextInt();
        for (int j=0;j<length ;j++ ) {
            if(ar[j]>x){
                if(ar[j]%x==0){
                    count++;
                }
            }
        }
        System.out.println("Count:"+count);
     }
}

上面的代码给出了正确的输出，但是复杂度是O(query*length)，如果数组大小太大，程序会超时。

谁能帮我优化问题？

Answer 1

您可以做的一项优化是利用 short-circuiting , 并使用一个 if 语句(而不是两个)。

所以改变这个:

if(ar[j]>x) {
  if(ar[j]%x==0) {

为此:

if(ar[j]>x && ar[j]%x==0) {

这不会影响您算法的时间复杂度，但会有所帮助 Branch Prediction .