java - 如何使用整数参数的二进制表示来过滤数组？

Question

>> 数字的二进制表示可用于从数组中选择元素。例如，

                 n: 88 = 23 + 24 + 26 (1011000)
                 array: 8, 4, 9, 0, 3, 1, 2
               indexes: 0  1  2  3  4  5  6
                 selected        *  *     *
                   result        0, 3,    2 so the result of filtering {8, 4, 9, 0, 3, 1, 2} using 88 would be {0, 3, 2} In the

above, the elements that are selected are those whose indices are used as exponents in the binary representation of 88. In other words, a[3], a[4], and a[6] are selected for the result because 3, 4 and 6 are the powers of 2 that sum to 88. Write a method named filterArray that takes an array and a non-negative integer and returns the result of filtering the array using the binary representation of the integer. The returned array must big enough to contain the filtered elements and no bigger. So in the above example, the returned array has length of 3, not 7 (which is the size of the original array.) Futhermore, if the input array is not big enough to contain all the selected elements, then the method returns null. For example, if n=3 is used to filter the array a = {18}, the method should return null because 3=20+21 and hence requires that the array have at least 2 elements a[0] and a1, but there is no a1. If you are using Java or C#, the signature of the function is int[ ] filterArray(int[ ] a, int n)

我有这个问题想要解决，我写了这段代码

public static int[] filterArray(int[] a, int n) {
    int[] x = new int[a.length];
    int j = 0;
    int count = 0;
    while (n > 0) {
        int digit = n % 2;
        n /= 2;
        x[j] = digit;
        j++;
    }

    System.out.println(Arrays.toString(a));

    System.out.println(Arrays.toString(x));

    for (int k = 0; k < x.length; k++) {
        if (x[k] == 1)
            count++;
    }

    System.out.println("count is " + count);

    int[] z = new int[count];
    for (int i = 0; i < z.length; i++) {
        for (int k = 0; k < x.length; k++) {
            if(x[k] == 1) {
                z[i] = a[k];
            }
        }
    }

    System.out.println(Arrays.toString(z));
    return x;

}

当我尝试使用测试数组进行测试时

System.out.println(Arrays.toString(filterArray(new int[] { 0, 9, 12, 18, -6 }, 11)));

它给了我以下输出

[18, 18, 18]

正确的输出是

[0, 9, 18]

Answer 1

问题是你的嵌套循环:你正在迭代输出数组的每个元素的整个输入数组，并继续用最后找到的元素覆盖这些值(使用调试器，你就会看到)。

要解决这个问题，请交换循环并跟踪“下一个”输出索引:

  int i = 0;
  for (int k = 0; k < x.length; k++) {
    if(x[k] == 1) {
        z[i] = a[k];
        i++; //advance the output index
    }
  }

这也会使您的代码更快，因为现在您的复杂度不再是 O(n²)，而只是 O(n)。