如何生成通过从 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

的倍数

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

How to generate a sequence created by removing all odd-indexed elements recursively from an Arraylist so that we get only 1 element at the end?

java

algorithm

sequence