There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.

Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of length n.

Example:

1
2
3
4
5
6
7
8
9
Input:
n = 9,
[1] 2 [3] 4 [5] 6 [7] 8 [9]
2 [4] 6 [8]
2 6
6
Output:
6

思路

对于这样的数列，1,2,3,4,…n：如果从左到右开始输出结果是i，则从右到左输出结果是n+1-i。

一趟操作之后，剩余的元素个数变成n/2，每一个元素对应为之前元素的两倍。如题目给出的示例。

如果[1,2,3,4]从左至右输出的结果是 f(4)，那么它从右至左输出的结果就是5-f(4)。

进一步推知，[2,4,6,8]从右到左输出的结果就是2*(5-f(4))。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int lastRemaining(int n) {
      if (n == 1){
          return 1;
      }
      else{
          return 2 * (n / 2 + 1 - lastRemaining(n / 2));
      }
    }
};

分享一个超时的暴力解法——实际上就是按照题目要求一直不停地删除元素，开销很大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public:
    int lastRemaining(int n) {
        vector<bool> visited(n);
        if (n < 1) return 0;
        else if (n == 1) return 1;
        else if (n > 1 && n <= 5) return 2;
        else{
            int final = 0;
            while(1){
                int i = 0;
                int count = 0;
                while(visited[i]) i++;
                while(i < n){
                    if (!visited[i]){
                        count++;
                        final = i;
                    }
                    if (count % 2 == 1) visited[i] = true;
                    i++;
                }
                if (count == 1){
                    break;
                }
                i = n - 1;
                count = 0;
                while(visited[i]) i--;
                while(i >= 0){
                    if(!visited[i]){
                        count++;
                        final = i;
                    }
                    if (count % 2 == 1) visited[i] = true;
                    i--;
                }
                if (count == 1){
                    break;
                }
            }
            return final+1;
        }
    }
};