給定一個從1 到 n 排序的整數(shù)列表。
首先，從左到右，從第一個數(shù)字開始，每隔一個數(shù)字進行刪除，直到列表的末尾。
第二步，在剩下的數(shù)字中，從右到左，從倒數(shù)第一個數(shù)字開始，每隔一個數(shù)字進行刪除，直到列表開頭。
我們不斷重復這兩步，從左到右和從右到左交替進行，直到只剩下一個數(shù)字。
返回長度為 n 的列表中，最后剩下的數(shù)字。
示例：
輸入:
n = 9,
1 2 3 4 5 6 7 8 9 （1,3,5,7,9被刪除）
2 4 6 8 （8,4被刪除）
2 6 （2被刪除）
6 （剩余6）
輸出:
6
答案：
1public int lastRemaining(int n) {
2 boolean left = true;
3 int remaining = n;
4 int step = 1;
5 int head = 1;
6 while (remaining > 1) {
7 if (left || ((remaining & 1) == 1)) {
8 head = head + step;
9 }
10 remaining = remaining >> 1;
11 step = step << 1;
12 left = !left;
13 }
14 return head;
15}
解析：
題描述的很清晰，就是先從左往右每隔一個就刪除一個數(shù)字，然后再從右往左每隔一個刪除一個數(shù)字……一直這樣循環(huán)下去，直到最后剩下一個數(shù)字為止。
在計算機編程中有個非常著名的算法題就是“約瑟夫環(huán)問題”，也稱“丟手絹問題”，如果對約瑟夫環(huán)問題比較熟悉的話，那么今天的這道題也就很容易理解了。如果不熟悉的話也沒關系，我們今天就詳細分析一下這道題。關于約瑟夫環(huán)問題不在今天所講的范圍之內(nèi)，后續(xù)有時間我們在單獨講解。
這題如果使用雙向鏈表或者是雙端隊列很好解決，因為雙向鏈表既可以從前往后刪除也可以從后往前刪除，當然這兩種方式都需要先初始化，今天我們講的這種方式是既沒有使用鏈表也沒有使用數(shù)組。
我們來看下上面的代碼，直接看可能不太直觀，我們可以把n想象成一個長度為n的數(shù)組，數(shù)組的元素是1,2,3,4,5……n，我們只需要記錄下每次刪除一遍之后數(shù)組的第一個元素即可，當remaining==1的時候就會退出while循環(huán)，最后返回數(shù)組的僅有的一個元素即可（這只是我們的想象，實際上操作的并不是數(shù)組，也沒有刪除，只是記錄，但原理都類似）。
boolean left = true;
代碼left判斷是否是從左往右刪除，如果為true表示的是從左往右刪除，如果為false表示的是從右往左刪除。
int remaining = n;
int step = 1;
int head = 1;
代碼remaining表示剩余的個數(shù)。step表示每次刪除的間隔的值，不是間隔的數(shù)量，比如1,2,3,4,5,6,7,8。第一次從左往右刪除的時候間隔值是1，刪除之后結果為2,4,6,8。第二次從右往左刪除間隔值就變?yōu)?了，刪除之后結果是2,6。然后第3次就變成4了。head表示的是記錄的剩余數(shù)字從左邊數(shù)第一個的值。
1 while (remaining > 1) {
2 if (left || ((remaining & 1) == 1)) {
3 head = head + step;
4 }
5 remaining = remaining >> 1;
6 step = step << 1;
7 left = !left;
8 }
第5-7行代碼很好理解，remaining表示的是剩余個數(shù)，每次刪除的時候都會剩余一半，所以除以2，也可以表示為往右移一位。step上面說了表示的是間隔值，每次循環(huán)之后都會擴大一倍，left就不在說了，一次往左一次往右……一種這樣循環(huán)。
我們主要來看下第2-4行代碼，如果是從這邊循環(huán)，那么第一個肯定是會被刪除的，第二個會成為head，而第二個值就是head+step；如果從右邊開始循環(huán)，如果數(shù)組的長度是奇數(shù)，那么第一個元素head也是要被刪除的，所以head值也要更新，代碼remaining&1==1判斷remaining是否是奇數(shù)。
我們以n=14為例，畫個圖來看下會更直觀一些
上面代碼變量比較多，實際上我們還可以改的更簡潔一些
1public int lastRemaining(int n) {
2 int first = 1;
3 for (int step = 0; n != 1; n = n >> 1, step++) {
4 if (step % 2 == 0 || n % 2 == 1)
5 first += 1 << step;
6 }
7 return first;
8}
注意這里的step不是刪除的間隔值，他是表示的是每刪除一遍就會加1，比如最開始從左往右刪除的時候step是0，然后再從右往左刪除的時候是1，然后再從左往右刪除的時候是2，然后再從右往左刪除的時候是3……，一直這樣累加。代碼很好理解，就不在過多解釋。
下面我們再來換種思路想一下
1，當我們從左往右消除的時候，比如[1,2,3,4]第一次從左往右消除的時候結果是[2,4]，也就是2*[1,2]
或者[1,2,3,4,5]第一次從左往右消除的時候結果也是[2,4]，也就是2*[1,2]
所以我們只需要計算數(shù)組前面一半的結果然后再乘以2即可。
2，當我們從右往左消除的時候，如果數(shù)組是偶數(shù)，比如[1,2,3,4,5,6]消除的結果是[1,3,5]，也就是2*[1,2,3]-1，如果數(shù)組是奇數(shù)的話，比如[1,2,3,4,5,6,7]消除的結果是[2,4,6]，也就是2*[1,2,3]。所以明白了這點，代碼就很容易想到了
1public int lastRemaining(int n) {
2 return leftToRight(n);
3}
4
5private static int leftToRight(int n) {
6 if (n <= 2)
7 return n;
8 return 2 * rightToLeft(n / 2);
9}
10
11private static int rightToLeft(int n) {
12 if (n <= 2)
13 return 1;
14 if (n % 2 == 1)
15 return 2 * leftToRight(n / 2);
16 return 2 * leftToRight(n / 2) - 1;
17}
我們再來思考一個問題，可以找一下規(guī)律
1，當n個數(shù)的時候，假設我們從左往右執(zhí)行，剩下的數(shù)字記為f1(n)（從數(shù)組[1,2,……n]開始），從右往左執(zhí)行，剩下的數(shù)字是f2(n)（從數(shù)組[n,n-1,……1]開始）。
2，如果我們記f1(n)在數(shù)組[1,2,……n]中的下標為k，那么f2(n)在數(shù)組中[n,n-1,……1]的下標也一定是k。所以我們可以得到f1(n)+f2(n)=n+1。
3，對于n個元素，執(zhí)行一次從左往右之后，剩下的[2,4,……n/2]就應該從右往左了，我們記他執(zhí)行，剩下的數(shù)字是f3(n/2)，所以我們可以得到f1(n)=f3(n/2)，f3(n/2)=2*f2(n/2)；
4，根據(jù)上面的3個公式
(1)：f1(n)+f2(n)=n+1
(2)：f1(n)=f3(n/2)
(3)：f3(n/2)=2*f2(n/2)
我們可以得出f1(n)=2*(n/2+1-f1(n/2))；并且當n等于1的時候結果就是1，所以代碼如下，非常簡單
1public int lastRemaining(int n) {
2 return n == 1 ? 1 : 2 * (1 + n / 2 - lastRemaining(n / 2));
3}
對于這道題的理解我們還可以來舉個例子，比如[1,2,3……n]，如果從左開始結果是k，那么從右開始結果就是n+1-k。比如[1,2,3,4,5,6,7,8,9,10]第一遍從左到右運算之后是[2,4,6,8,10]，假如[1,2,3,4,5]從左到右的結果是f(5)，那么他從右到左的結果就是5+1-f(5)，也就是6-f(5)，所以[2,4,6,8,10]從右到左的結果就是2*(6-f(5))，所以我們可以得出f(10)=2*(6-f(5))，所以遞推公式就是f(n)=2*(n/2+1-f(n/2))。
我們還可以把上面遞歸的代碼改為非遞歸，這個稍微有一定的難度
1public int lastRemaining(int n) {
2 Stack<Integer> stack = new Stack<>();
3 while (n > 1) {
4 n >>= 1;
5 stack.push(n);
6 }
7 int result = 1;
8 while (!stack.isEmpty()) {
9 result = (1 + stack.pop() - result) << 1;
10 }
11 return result;
12}
下面再來思考一下，看能不能再優(yōu)化一下，我們讓left(n)=left[1,2,3,……n]表示從左往右執(zhí)行之后，剩下的數(shù)字，right(n)=right[1,2,3,……,n]表示從右往左執(zhí)行之后，剩下的數(shù)字，所以我們可以得出一個結論
1，left(1)=right(1)=1;
2，left(2k)=left[1,2,3,……2k]=right[2,4,6,……2k]=2*right(k)；
3，left(2k+1)=left[1,2,3,……2k,2k+1]=right[2,4,6,……2k]=2*right(k)；
4，right(2k)=right[1,2,3,……2k]=left[1,3,5,……2k-1]=left[2,4,6,……2k]-1=2*left(k)-1
5，right(2k+1)=right[1,2,3,……2k,2k+1]=left[2,4,6,……2k]=2*left(k)。
6，left(4k)=left(4k+1)=4*left(k)-2；
7，left(4k+2)=left(4k+3)=4*left(k)；
搞懂了上面的規(guī)律，代碼就呼之欲出了，下面我們來看下代碼
1public int lastRemaining(int n) {
2 if (n < 4)
3 return (n == 1) ? 1 : 2;
4 return (lastRemaining(n / 4) * 4) - (~n & 2);
5}
我們再來看最后一種解法，也是一行代碼搞定
1public int lastRemaining(int n) {
2 return ((Integer.highestOneBit(n) - 1) & (n | 0x55555555)) + 1;
3}
如果對約瑟夫環(huán)問題比較熟練的話，那么這種解法就比較好理解了，其實他就是約瑟夫環(huán)中k=2的一個問題。
聯(lián)系客服
