如何生成通过从Arraylist中递归删除所有奇数索引元素而创建的序列，以便最后只得到1个元素？

Question

我在ArrayList中有一个数字列表。我正在尝试从列表中删除奇数索引编号。我们需要循环执行此操作，直到它在列表中仅保留1个元素为止。

示例：
列表 -> {1,2,3,4,5,1,2,3,4,5}
在
迭代1之后删除奇数索引元素后的列表： {
2,4,1、3,5 } 迭代2 ： {
4，3 } 迭代3： {3}

蛮力方法有效，但是还有其他方法吗？列表中的元素数量可能很大，直到10 ^ 18。

private static int getLastNumber(ArrayList<Integer> list)
    {
        int size = list.size();
        for (int i = 1; i<=size; i++) {
            if (i%2 != 0) {
                list.set(i-1, -1);
            }
        }
        for (int i = 0; i<list.size(); i++) {
            if (list.get(i) == -1) {
                list.remove(i);
            }
        }
        if (list.size() == 1) {
            return list.get(0);
        } else {
            return getLastNumber(list);
        }
    }

Answer 1

实际上，这很容易：给定一个元素列表，返回的索引是两个最接近但小于列表大小的幂。

1 -> 1
2 -> 2
3 -> 2
4 -> 4
5 -> 4
6 -> 4
7 -> 4
8 -> 8
...

您可以使用位掩码轻松完成此操作：

public static int getIndex(int a){
    for (int i = 31; i >= 0; i--) {
        if (((a >> i) & 1) == 1)
            return i;
    }

    return 0;
}

public static void main(String []args){
    int a = 10;

    double index = Math.pow(2, getIndex(a));
    System.out.println(index);  
}

至少对我来说，证明不那么容易。这可以帮助您更好地可视化它：

level
0        1  2  3  4  5  6  7  8  9  ...
1           2     4     6     8
2                 4           8
3                             8

就像每次迭代一样，您将保持 2^level