【劍指Offer學習】【面試題45:圓圈中最後剩下的數字(約瑟夫環問題)】

【劍指Offer學習】【面試題45:圓圈中最後剩下的數字(約瑟夫環問題)】

題目:0, 1, … , n-1 這n個數字排成一個圈圈,從數字0開始每次從圓圏裡刪除第m個數字。求出這個圈圈裡剩下的最後一個數字。


解題思路

第一種:經典的解法, 用環形連結串列模擬圓圈。
  建立一個總共有n 個結點的環形連結串列,然後每次在這個連結串列中刪除第m 個結點。

程式碼實現

public static int lastRemaining(int n, int m) {
if (n < 1 || m < 1) {
return -1;
}
List<Integer> list = new LinkedList<>();
for (int i = 0; i < n; i  ) {
list.add(i);
}
// 要刪除元素的位置
int idx = 0;
// 開始計數的位置
int start = 0;
while (list.size() > 1) {
// 只要移動m-1次就可以移動到下一個要刪除的元素上
for (int i = 1; i < m; i  ) {
idx = (idx   1) % list.size(); // 【A】
}
list.remove(idx);
// 確保idx指向每一輪的第一個位置
// 下面的可以不用,【A】已經可以保證其正確性了,可以分析n=6,m=6的第一次刪除情況
//  if (idx == list.size()) {
//      idx = 0;
//  }
}
return list.get(0);
}

第二種:分析法
  首先我們定義一個關於n 和m 的方程町磯時,表示每次在n 個數字0,1, … , n-1中每次刪除第m 個數字最後剩下的數字。
  在這n個數字中, 第一個被刪除的數字是(m-1)%n. 為了簡單起見,我們把(m- 1)%n 記為k,那麼刪除k之後剩下的n-1個數字為0, 1, … , k-1,k 1, … , n-1,並且下一次刪除從數字k 1開始計數。相當於在剩下的序列中, k 1排在最前面,從而形成k 1, .. . , n- 1, 0, I, … , k-1 。該序列最後剩下的數字也應該是關於n 和m 的函式。由於這個序列的規律和前面最初的序列不一樣(最初的序列是從0 開始的連續序列),因此該函式不同於前面的函式,記為f’(n-1,m)。最初序列最後剩下的數字f(n, m)一定是刪除一個數字之後的序列最後剩下的數字,即f(n, m)=f’(n-1, m)。
  接下來我們把剩下的這n-1個數字的序列k-1, …, n-1, 0, 1, … , k-1做一個對映,對映的結果是形成一個從0 到n-2的序列:
  
這裡寫圖片描述

程式碼實現

public static int lastRemaining2(int n, int m) {
if (n < 1 || m < 1) {
return -1;
}
int last = 0;
for (int i = 2; i <=n ; i  ) {
last = (last   m)%i;
}
return last;
}

完整程式碼

import java.util.LinkedList;
import java.util.List;
public class Test45 {
public static int lastRemaining(int n, int m) {
if (n < 1 || m < 1) {
return -1;
}
List<Integer> list = new LinkedList<>();
for (int i = 0; i < n; i  ) {
list.add(i);
}
// 要刪除元素的位置
int idx = 0;
// 開始計數的位置
int start = 0;
while (list.size() > 1) {
// 只要移動m-1次就可以移動到下一個要刪除的元素上
for (int i = 1; i < m; i  ) {
idx = (idx   1) % list.size(); // 【A】
}
list.remove(idx);
// 確保idx指向每一輪的第一個位置
// 下面的可以不用,【A】已經可以保證其正確性了,可以分析n=6,m=6的第一次刪除情況
//  if (idx == list.size()) {
//      idx = 0;
//  }
}
return list.get(0);
}
public static int lastRemaining2(int n, int m) {
if (n < 1 || m < 1) {
return -1;
}
int last = 0;
for (int i = 2; i <=n ; i  ) {
last = (last   m)%i;
}
return last;
}
public static void main(String[] args) {
test01();
System.out.println();
test02();
}
private static void test01() {
System.out.println(lastRemaining(5, 3)); // 最後餘下3
System.out.println(lastRemaining(5, 2)); // 最後餘下2
System.out.println(lastRemaining(6, 7)); // 最後餘下4
System.out.println(lastRemaining(6, 6)); // 最後餘下3
System.out.println(lastRemaining(0, 0)); // 最後餘下-1
}
private static void test02() {
System.out.println(lastRemaining2(5, 3)); // 最後餘下3
System.out.println(lastRemaining2(5, 2)); // 最後餘下2
System.out.println(lastRemaining2(6, 7)); // 最後餘下4
System.out.println(lastRemaining2(6, 6)); // 最後餘下3
System.out.println(lastRemaining2(0, 0)); // 最後餘下-1
}
}

執行結果

這裡寫圖片描述