元素的排列避免连续位置上的重复

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