算法面试题--正负交替

浏览数：23 / 时间：2015年06月08日

给一个包含正负整数的数组，要求对这个数组中的数进行重新排列，使得其正负交替出现。首先出现负数，然后是正数，然后是负数。有多余的一方，就放在末尾。

如 [1,2,3,-4]->[-4,1,2,3]
[1,-3,2,-4,-5]->[-3,1,-4,2,-5]

要求:使用O(1)的空间
问1：如果需要保持正数序列和负数序列各自原来的顺序，如何做，时间复杂度是多少？
问2：如果不需要保持正数序列和负数序列各自原来的顺序，如何做，时间复杂度是多少？

思路分析：题目要求只能使用O(1)的空间复杂度，也就是只能借助一个零时变量，想到如下思路，依次遍历数组中的每个元素，如果处在偶数位置的数是负数，处在奇数位置的数是正数就保持不变；如果处在偶数位置的数是正数，就该位置的下一个位置依次向后找到第一为负数的数，然后移动将找到的负数移动到偶数的位置（借助零时变量），同理对应处在奇数位置的数负数做类似的处理。

问1和问2的不同地方在于对处在偶数位置的数是正数或处在奇数位置的数是负数处理，问1因要保持原来的顺序，所以要依次移动元素，而问2不需要保持原来的顺序，所以可以直接交换。

问1代码，时间复杂度O(n^2)：

void sortA(int arr[], int n)
{
	for (int i = 0; i < n; i++)
	{
		if (i % 2 == 0 && arr[i] < 0)
			continue;
		if (i % 2 == 1 && arr[i]>0)
			continue;
		if (i % 2 == 0 && arr[i]>0)
		{
			int j;
			int temp;
			for (j = i + 1; j < n && arr[j]>0; j++);
			if (j == n) break;
			else
			{
				temp = arr[j];
				for (; j > i; j--)
				{
					arr[j] = arr[j - 1];
				}
				arr[i] = temp;
			}
		}
		if (i % 2 == 1 && arr[i]<0)
		{
			int j;
			int temp;
			for (j = i + 1; j < n && arr[j]<0; j++);
			if (j == n) break;
			else
			{
				temp = arr[j];
				for (; j > i; j--)
				{
					arr[j] = arr[j - 1];
				}
				arr[i] = temp;
			}
		}
	}
}

问2代码，时间复杂度O(n)：

void sortB(int arr[], int n)
{
	for (int i = 0; i < n; i++)
	{
		if (i % 2 == 0 && arr[i] < 0)
			continue;
		if (i % 2 == 1 && arr[i]>0)
			continue;
		if (i % 2 == 0 && arr[i]>0)
		{
			int j;
			int temp;
			for (j = i + 1; j < n&&arr[j]>0; j++);
			if (j == n) break;
			else
			{
				temp = arr[j];
				arr[j] = arr[i];
				arr[i] = temp;
			}
		}
		if (i % 2 == 1 && arr[i]<0)
		{
			int j;
			int temp;
			for (j = i + 1; j < n && arr[j]<0; j++);
			if (j == n) break;
			else
			{
				temp = arr[j];
				arr[j] = arr[i];
				arr[i] = temp;
			}
		}
	}
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

算法面试题--正负交替