元素的排列避免連續位置上的重複

Question

我有一個包含N元素的數組，我有M數字。 U需要排列M（1，2，3，... M）個數字，重複M中的數字。這樣陣列中的構成元素就不一樣了。

例如：N=9和M=3[4, 4, 1]意味着1在陣列中出現4次，'2'出現4次，3出現一次。

所以可能的安排將是[1,2,1,2,1,2,3,1,2]。

例如：N=8和M=2[3, 5]。

沒有可能將元素排列成兩個連續的元素不相同。

我需要找到天氣安排是可能與否。

Answer 1

嘗試是這樣的（Java語法）：

int max = M[0]; 
int sum = M[0]; 
for (i = 1 ; i < M.length ; i++) { 
    if (M[i] > max) { 
     max = M[i]; 
    } 
    sum = sum + M[i]; 
} 

if (2*max <= s+1) { 
    System.out.println("possible"); 
} else { 
    System.out.println("NOT possible"); 
} 

時間複雜度：O（| M |）

---

的想法是，如果你想這些數字放到一個數組，您將從最長的序列開始，然後您選擇第一個最長的序列以避免重複。

E.g.: 
----------- arr: [] 
1, 1, 1, 1 
2, 2 
3 
----------- arr: [1] 
1, 1, 1 
2, 2 
3 
----------- arr: [1, 2] 
1, 1, 1 
2 
3 
----------- arr: [1, 2, 1] 
1, 1 
2 
3 
----------- arr: [1, 2, 1, 2] 
1, 1 
3 
----------- arr: [1, 2, 1, 2, 1] 
1 
3 
----------- arr: [1, 2, 1, 2, 1, 3] 
1 
----------- arr: [1, 2, 1, 2, 1, 3, 1] 

所以，如果從M中的最大數目是在其他大部分+ 1的總和，這是可能的，以獲得陣列而不重複：

max <= sum_of_the_others + 1  | + max 

這相當於

max + max <= sum_of_all_numbers + 1 

相當於

2*max <= sum_of_all_numbers + 1