奇数位丢弃(C++、Python)

美团2016招聘笔试：奇数位丢弃

对于一个由0…n的所有数按升序组成的序列，我们要进行一些筛选，每次我们取当前所有数字中从小到大的第奇数位个的数，并将其丢弃。重复这一过程直到最后剩下一个数。请求出最后剩下的数字。

输入描述:
多组数据，每组数据一行一个数字，为题目中的n(n<=1000)。

输出描述:
一行输出最后剩下的数字。

输入例子:

500
1

输出例子:

255
1

Tips：以下所有代码经过实测提交可以AC，大家可以放心阅读

思路一 (循环删除法，时间复杂度O(N^2)，空间复杂度O(N))

常规思路，多次循环，每次都将当前列表中奇数位的数字删除，直到最后列表中只剩下一个数字为止

C++代码

#include
using namespace std;
int main() {
	int n;
	while (cin >> n) {
		vector<int> v(n + 1);
		iota(v.begin(), v.begin() + n + 1, 0);
		while (v.size() != 1) {
			for (int j = 0; j < int(v.size()); j++)
				v.erase(v.begin() + j);
		}
		cout << v[0] << endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Tips：iota函数是C++STL中对容器进行递增初始化的函数，传参方式如下
      iota(指向可迭代区间开头的迭代器，指向可迭代区间末尾的迭代器，初始值)
1
2

Python代码

while True:
    try:
        ls = [int(i) for i in range(int(input()) + 1)]
        while len(ls) != 1:
            del ls[0::2]
        print(ls[0])
    except EOFError:
        break
1
2
3
4
5
6
7
8

思路二 (位运算法，时间复杂度O(logN)，空间复杂度O(1))

结论：0到n的二进制情况下1的个数最多的那个数就是最后剩下的

思路：由于下标是从0开始的，所以第一次移走的是二进制下最右边为0的位置（从0开始的偶数位置）上的数，然后第二轮各个数的位置等于原先的除以2，就是从原本的位置到>>1后的位置，再次移走二进制下最右边为0的位置（1(01) 5(101) 9(1001) ……它们第二轮所对应的位置是0， 2， 4），那这样的话最后剩一个数肯定是0到n中二进制下1最多的那个数，毕竟它每一次的位置都是奇数

C++代码

#include
using namespace std;
int main() {
	int n;
	while (cin >> n) {
		int bit = 1;
		while (bit <= n + 1) {
			bit <<= 1;
		}
		cout << (bit >> 1) - 1 << endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

Python代码：

while True:
    try:
        n, bit = int(input()), 1
        while bit <= n + 1:
            bit <<= 1
        print((bit >> 1) - 1)
    except EOFError:
        break
1
2
3
4
5
6
7
8

Tips：一定不能直接返回bit，因为首位置1左移补0得到偶数bit，减1得最大奇数bit；考虑到奇数n的情况，所以要超前左移1最终右移1确保bit-1为末尾值，我在这个坑里花了不少时间才爬出来

思路三（数学公式法，时间复杂度O(N)，空间复杂度O(1)）

思路：其实本质思想和前面一个差不多，只不过使用函数方便了运算

C++代码

#include
using namespace std;
int main() {
	int n;
	while (cin >> n) {
		int bit = log(n + 1) / log(2);
		cout << ((1 << bit) - 1) << endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10

Python代码

from math import *

while True:
    try:
        print((1 << int(log(int(input()), 2))) - 1)
    except EOFError:
        break
1
2
3
4
5
6
7