Java 中不相等的相邻元素

给定一个包含 n 个（正数或负数）数字的数组 inArr。任务是返回重新排列元素的数组，使得没有两个相邻的元素相等。如果有多个有效的排列，则可以返回任何一个有效的排列。如果输入数组不包含任何有效的排列，则可以在控制台上显示适当的消息。

示例 1

输入

int inArr[] = {7, 7, 6, 8}

输出 {7, 6, 7, 8}

解释：有许多有效的排列是可能的。这些有效的排列如下所示：{7, 6, 7, 8}, {7, 6, 8, 7}, {7, 8, 7, 6}, {7, 8, 6, 7}, {8, 7, 6, 7}, {6, 7, 8, 7}。其中 {7, 6, 7, 8} 在输出中列出。

示例 2

输入

int inArr[] = {2, 4, 8, 9, 5, 7, 3, 6, 1}

输出 {2, 4, 8, 9, 5, 7, 3, 6, 1}

解释：输入数组的给出方式使得没有任何两个元素具有相同的值。因此，输入数组本身就是答案。

示例 3

输入

int arr[] = {3, 3, 3, 3, 3}

输出：不可能有有效的排列，其中相邻元素的值不同。

解释：所有元素的值都相同。因此，不可能有有效的排列。

方法：暴力法

在此方法中，我们计算输入数组的所有排列。如果出现任何有效的排列，我们则返回该排列。如果没有有效的排列是可能的，则显示适当的消息。

为了计算有效的排列，首先，我们将数组按升序排序。然后，我们将找到已排序数组的下一个排列，并检查它是否是有效的排列。如果它是有效的排列，则我们可以返回该排列。如果不是，那么我们将找到下一个排列，并继续这样做，直到找到一个有效的排列或所有的排列都已用尽。如果排列都已用尽，那么我们可以说给定输入数组没有有效的排列，这在以下程序中有所说明。

文件名： UniqueAdjEle.java

输出

For the input array: 
7 7 6 8 
The valid arrangement is: 
6 7 8 7 

For the input array: 
2 4 8 9 5 7 3 6 1 
The valid arrangement is: 
2 4 8 9 5 7 3 6 1 

For the input array: 
3 3 3 3 3 
The valid arrangement is not possible.

复杂度分析：由于程序正在计算排列，因此程序的时间复杂度为 O(N!)，其中 N 是链表中存在的元素总数。该程序使用常数空间；因此，程序空间复杂度为 O(1)。

上述程序不适用于较大的输入，因为程序的时间复杂度太高。因此，我们必须进行一些优化以降低时间复杂度。

方法：使用 Set

这是一个贪心方法，其中我们首先放置出现次数最多的元素。使用集合，我们将所有元素按其出现次数的顺序放置。以下是计算答案的步骤。

步骤 1：声明一个空数组或列表 solAl。

步骤 2：对数组或列表 solAl 进行排序。

步骤 3：声明一个集合 st，用于存储元素及其出现次数。

步骤 4：遍历列表或数组 solAl

• 迭代直到每次都遇到相同的元素。将元素计数加 1。将元素和该元素的出现次数放入集合 st 中。

步骤 5：创建一个临时变量，用于存储前一个元素及其出现次数。

步骤 6：当集合 st 不为空时，执行以下操作：

• 提取最后一个元素并将其添加到结果中。从集合 st 中删除该元素。
• 将弹出元素的出现次数减 1。
• 如果前一个元素的出现次数非零，则将其放入集合中。
• 当前元素应被视为下一次迭代的前一个元素。

步骤 7：最终，返回列表或数组 solAl。

实施

上述步骤的实现如下。

文件名： UniqueAdjEle.java

输出

For the input array: 
7 7 6 8 
The valid arrangement is: 
7 8 7 6 

For the input array: 
2 4 8 9 5 7 3 6 1 
The valid arrangement is: 
2 4 8 9 5 7 3 6 1 

For the input array: 
3 3 3 3 3 
The valid arrangement is not possible.

复杂度分析：由于程序使用了排序，因此程序的时间复杂度为 O(N * log(N))。程序使用集合来存储元素及其出现次数。程序还使用了一个辅助数组 (arr)。因此，程序空间复杂度为 (N)，其中 N 是输入数组中存在的元素总数。

注意：可以使用优先队列代替集合。在这种情况下，时间复杂度和空间复杂度也保持不变。