filterArray

美国程序员面试题：

A binary representation of a number can be used to select elements from an array. For example,
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 a[1], but there is no a[1].
If you are using Java or C#, the signature of the function is
int[ ] filterArray(int[ ] a, int n)
If you are using C or C++, the signature of the function is
int * filterArray(int a[ ], int len, int n) where len is the length of the array a Hint: Proceed as follows
a. Compute the size of the returned array by counting the number of 1s in the binary representation of n (You can use modulo 2 arithmetic to determine the 1s in the binary represention of n)
b. Allocate an array of the required size
c. Fill the allocated array with elements selected from the input array

测试样例

java实现代码：

package com.zzy;

import java.util.ArrayList;
import java.util.Objects;

/**
 * 更多请关注: http://huamaodashu.com
 * Created by huamaodashu on 24/07/2018.
 */
public class filterArray {
    public static void main(String[] args) {

//        int []a ={9, -9,5};
        int []a ={0,9,12,18,-6};
//        int []a ={9, -9};
        int n = 11;
        System.out.println(indexArray(a,n));

    }


    public static int[] indexArray(int[ ] a,int n){
        int[] arry = {};

        if(n==0){
            return arry;
        }
        ArrayList arrayList = new ArrayList();

        int count =0;

        while (true){


            if(n%2==0){


            }else if(n%2==1){
//                arrayList.add(1);


                if(count>= a.length){
                    return null;
                }

                arrayList.add(a[count]);

//                System.out.println("count"+a[count]);
            }
            if (n==1){
                break;
            }
            count++;
            n=n/2;

        }

        int [] arrya = new int[arrayList.size()];
        System.out.println("arrayList.size()"+arrayList.size());

        for (int i = 0; i < arrayList.size(); i++) {

            System.out.println("i="+i);
            arrya[i]= (int) arrayList.get(i);
            System.out.println("count"+arrya[i]);
        }

        return arrya;

    }
}