用于在 O(n)时间和 O(1)额外空间中重新排列正数和负数的 Java 程序
原文:https://www . geeksforgeeks . org/Java-program-for-重排-正数和负数-on-time-O1-extra-space/
数组包含随机顺序的正数和负数。重新排列数组元素，使正数和负数交替出现。正数和负数的数量不必相等。如果有更多的正数，它们会出现在数组的末尾。如果有更多的负数，它们也会出现在数组的末尾。 例如，如果输入数组是[-1，2，-3，4，5，6，-7，8，9]，那么输出应该是[9，-7，8，-3，5，-1，2，4，6] 注:划分过程改变元素的相对顺序。也就是说，用这种方法不能保持元素出现的顺序。维护本问题中元素的出现顺序见本。 解决方法是先用 QuickSort 的划分过程将正数和负数分开。在划分过程中，将 0 视为透视元素的值，以便所有负数都放在正数之前。一旦负数和正数被分开，我们从第一个负数和第一个正数开始，用下一个正数交换每个交替的负数。
Java 语言(一种计算机语言，尤用于创建网站)
// A JAVA program to put positive numbers at even indexes
// (0, 2, 4,..) and negative numbers at odd indexes (1, 3,
// 5, ..)
import java.io.*;
class Alternate {
// The main function that rearranges elements of given
// array. It puts positive elements at even indexes (0,
// 2, ..) and negative numbers at odd indexes (1, 3, ..).
static void rearrange(int arr[], int n)
{
// The following few lines are similar to partition
// process of QuickSort. The idea is to consider 0
// as pivot and divide the array around it.
int i = -1, temp = 0;
for (int j = 0; j < n; j++)
{
if (arr[j] < 0)
{
i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Now all positive numbers are at end and negative numbers at
// the beginning of array. Initialize indexes for starting point
// of positive and negative numbers to be swapped
int pos = i+1, neg = 0;
// Increment the negative index by 2 and positive index by 1, i.e.,
// swap every alternate negative number with next positive number
while (pos < n && neg < pos && arr[neg] < 0)
{
temp = arr[neg];
arr[neg] = arr[pos];
arr[pos] = temp;
pos++;
neg += 2;
}
}
// A utility function to print an array
static void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
/*Driver function to check for above functions*/
public static void main (String[] args)
{
int arr[] = {-1, 2, -3, 4, 5, 6, -7, 8, 9};
int n = arr.length;
rearrange(arr,n);
System.out.println("Array after rearranging: ");
printArray(arr,n);
}
}
/*This code is contributed by Devesh Agrawal*/
输出:
4 -3 5 -1 6 -7 2 8 9
时间复杂度: O(n)，其中 n 为给定数组中的元素个数。 辅助空间: O(1)
更多详情请参考整篇文章在 O(n)时间和 O(1)额外空间重新排列正负数！
版权属于：月萌API www.moonapi.com，转载请注明出处
