1 class Solution { 2 public: 3 int lastRemaining(int n) { 4 if (n == 1) return 1; 5 return 2 * (n / 2 + 1 - lastRemaining(n / 2)); 6 7 // vector<int> t; 8 // for (int i = 1; i <= n; i++) t.push_back(i); 9 // bool flag1 = true; 10 // while (t.size() > 1) { 11 // // cout << t.size() << endl; 12 // vector<int> tmp; 13 // bool flag2 = false; 14 // if (flag1) { 15 // for (int i = 0; i < t.size(); i++) { 16 // if (flag2) tmp.push_back(t[i]); 17 // flag2 = !flag2; 18 // } 19 // } else { 20 // for (int i = t.size() - 1; i >= 0; i--) { 21 // if (flag2) tmp.insert(tmp.begin(), t[i]); 22 // flag2 = !flag2; 23 // } 24 // } 25 26 // t.clear(); 27 // t = tmp; 28 // flag1 = !flag1; 29 // } 30 31 // return t[0]; 32 } 33 };
算法思路：数学题。
1.设n个数时，从左到右开始执行剩下的数为f1(n)，将n个数反转后(即：n,n-1,...,1)，从左到右执行剩下的数为f2(n)
2.则，f1(n)和f2(n)剩下的数，在他们在各自原数组中的下标一定一样，即两者剩余的数都是下标i位置处的元素。1,...,n和n,...,1两个相同下标的元素相加为n+1
3.那么f2(n)的元素怎么得到？对于2n个元素，执行一次从左到右之后，剩余的元素除以2，可以得到1,...,n的元素。
4.如果继续执行，相当于对1,...,n的元素从右到左开始执行(因为第一次已经从左到右执行了)，等价于：对于1,...,n元素从右到左执行的结果*2，即：f1(2n) = 2 * f2(n)
5.所有得到递推式：f1(n) + f2(n) = n + 1 又由于f2(n) * 2 = f1(2n) 所以：f1(n) + f1(2n) / 2 = n + 1;
6.用n/2替换n得到：f1(n/2) + f1(n) / 2 = n / 2 + 1 -----> f1(n) = 2 * (n / 2 + 1 - f1(n / 2))