用于将数组转换为之字形的 Java 程序
给定一个 DISTINCT 元素的数组，在 O(n)时间内以之字形方式重新排列数组的元素。转换后的数组应该是ace<f的形式。
例:
输入 : arr[] = {4，3，7，8，6，2，1} 输出 : arr[] = {3，7，4，8，2，6，1}
输入 : arr[] = {1，4，3，2} 输出 : arr[] = {1，4，2，3}
一个简单的解决方案是先对数组进行排序。排序后，排除第一个元素，成对交换其余元素。(即保持 arr[0]不变，交换 arr[1]和 arr[2]，交换 arr[3]和 arr[4]，等等)。 时间复杂度 : O(N log N)既然我们需要先对数组进行排序。
我们可以使用高效方法在 O(n) 时间内转换。这个想法是使用一个经过修改的冒泡排序。
- 维护一个标志，用于表示我们当前需要哪个订单(即< or >)。
- 如果当前的两个元素不是按这个顺序排列的，那么交换这些元素，否则就不是。
让我们看看使用三个连续元素 A、B、c 的主要逻辑。
假设我们当前正在处理 B 和 C，当前关系是‘C’，因为当前关系是‘’，即 A 必须大于 B，所以关系是 A > B and B > C，我们可以推导出 A > C，所以如果我们交换 B 和 C，那么关系是 A > C 和 C < B. Finally we get the desired order A C B 更多解释请参考这个。
下图是上述方法的模拟运行:
下面是上述方法的实现:
Java 语言(一种计算机语言，尤用于创建网站)
// Java program to sort an array
// in Zig-Zag form
import java.util.Arrays;
class Test
{
static int arr[] = new int[]{4, 3, 7,
8, 6, 2, 1};
// Method for zig-zag conversion
// of array
static void zigZag()
{
// Flag true indicates relation "<"
// is expected, else ">" is expected.
// The first expected relation is "<"
boolean flag = true;
int temp =0;
for (int i=0; i<=arr.length-2; i++)
{
// "<" relation expected
if (flag)
{
/* If we have a situation like
A > B > C, we get A > B < C
by swapping B and C */
if (arr[i] > arr[i+1])
{
// swap
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
// ">" relation expected
else
{
/* If we have a situation like
A < B < C, we get A < C > B
by swapping B and C */
if (arr[i] < arr[i+1])
{
// swap
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
}
// flip flag
flag = !flag;
}
}
// Driver code
public static void main(String[] args)
{
zigZag();
System.out.println(Arrays.toString(arr));
}
}
输出:
3 7 4 8 2 6 1
时间复杂度:O(n) T3】辅助空间: O(1)
更多详情请参考将数组转换成之字形的完整文章！
'>',>
版权属于：月萌API www.moonapi.com，转载请注明出处
