时间戳

首页 > 解决方案 > 在两个极限之间找到 3 和 5 的所有倍数 - 复杂性

java - 在两个极限之间找到 3 和 5 的所有倍数 - 复杂性

问题描述

我正在尝试查找 1 到 10000000（包括两者）之间的所有数字。我尝试了两种解决方案

  1. 蛮力方法：循环从 1 到 10000000 的所有数字，并找到所有可以被 3 或 5 或两者整除的数字。
  2. 分而治之的方法：有 4 个计数器（2 个从开始，2 个从结束）。2 个计数器适用于 3 的倍数，两个适用于 5 的倍数。我将所有倍数放在一个 Set 中（我不需要排序元素，我只需要元素，排序也增加了我的复杂性）。

但是，循环方法比“分治法”花费的时间更短（大约少 10 倍）。我也在网上搜索了解决方案。但是，我只能找到循环方法。我的方法中是否缺少某些东西会增加我的执行时间？请指出这一点。我从 List 开始，移动到 Sorted Set，然后最终确定使用 HashSet，但似乎需要时间。

这是我尝试过的。

`

public static void main(String[] args) {

    System.out.println("Numbers divisible by 3 and 5:");

    nosDivisibleBy3And5();    // divide & conquer approach (approach to consider)

    nosDivisibleBy3And5BruteForce();

}

private static void nosDivisibleBy3And5BruteForce() {

    IntStream ar = IntStream.range(1, 10000001);  // start inclusive, end exclusive

    Integer[] array = ar.boxed().toArray(Integer[]::new);

    List<Integer> list = new ArrayList<>();

    int count = 0;

    long start = System.currentTimeMillis();

    /* 
     * Traversing array from 1 to 100, 
     * if it is either divisible by 3 or 5 or both, count it , print it. 
     * 
     */
    for(int i = 0; i < array.length ; i ++) {

        if((array[i] % 3 == 0) || (array[i] % 5 == 0)) {

            //System.out.println(array[i]);

            list.add(array[i]);

            count++;
        }
    }
    long end = System.currentTimeMillis();

    System.out.println("Brute Force Approach:");
    System.out.println("No of elements counted: " + count);

    //Collections.sort(list);

    //System.out.println("Elements: " + list);

    System.out.println("Time: " + (end - start));

}

private static void nosDivisibleBy3And5() {

    /* 
     * Set has all those numbers which 
     * are divisible by both 3 and 5.
     * 
     */

    Set<Integer> elementsSet = new HashSet<Integer>();

    int fr3,
    fr5,
    mid,
    count;

    fr3 = 2;   // fr3 indicates the index of the first value divisible by 3.
    fr5 = 4;   // fr5 indicates the index of the first value divisible by 5.
    count = 0;

    int end3 = 9999998 , // end3 indicates the index of the last value divisible by 3.
            end5 = 9999999;   // end5 indicates the index of the last value divisible by 5.

    /* Getting all the numbers from 1 to 100 from Intstream object */
    IntStream ar = IntStream.range(1, 10000001);  // start inclusive, end exclusive

    Integer[] array = ar.boxed().toArray(Integer[]::new);

    /* 
     * Using divide and conquer approach , mid divides the array from 1 to 100
     * in two parts, on the first fr3 and fr5 will work, on the second part end3 
     * and end5 will work.
     */
    mid = (fr3 + end3)/2;

    long start = System.currentTimeMillis();

    while(fr3 <= mid && end3 >= mid) {

        elementsSet.add(array[fr3]);

        elementsSet.add(array[fr5]);

        elementsSet.add(array[end3]);

        elementsSet.add(array[end5]);

        fr3 += 3;
        fr5 += 5;
        end3 -= 3;
        end5 -= 5;
    }

    long end = System.currentTimeMillis();

    System.out.println("Our approach");
    System.out.println("No of elements counted: " + elementsSet.size());


    //System.out.println("Elements:" + elementsSet);
    System.out.println("Time:  " + (end - start));
}

}

`

标签： javaalgorithmdata-structurestime-complexitydivide-and-conquer

解决方案

HashSet 在散列和检查元素是否已经存在并且比裸 ArrayList 慢add()

如果您的问题真的是找到所有可被 3 或 5 整除的数字，那么您可以使用具有预定长度的数组：

int from = 1;
int to = 1000000;
int d3 = (to / 3) - (from / 3) + (from % 3 == 0 ? 1 : 0); // how many divisible by 3
int d5 = (to / 5) - (from / 5) + (from % 5 == 0 ? 1 : 0); // how many divisible by 5
int d15 = (to / 15) - (from / 15) + (from % 15 == 0 ? 1 : 0); // how many divisible by 15

int[] array = new int[d3 + d5 - d15]; // counted 15's twice

int offset = 0;
for (int i = from; i <= to; i++) {
  if (i % 3 == 0 || i % 5 == 0) array[offset++] = i;
}

推荐阅读