题目:输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,
所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
针对这个题目,我们可以维护两个指针,一个指针指向数组的第一个数字,向后移动;一个指针指向最后一个数字,向前移动。分四种情况:
1.如果后一个指针指向奇数而前一个指针指向偶数,则交换两个数;之后,前一个指针继续向后移动,后一个指针继续向前移动;
2.如果后一个指针指向奇数而前一个也指针指向奇数,则前一个指针继续向后移动,后一个指针位置不变;
3.如果后一个指针指向偶数而前一个指针也指向偶数,则前一个指针位置不变,后一个指针继续向前移动;
4.如果后一个指针指向偶数而前一个指针指向奇数,则前一个指针继续向后移动,后一个指针继续向前移动;
public class Test {
public static void main(String[] args)
{
oddEvenSort(new int[]{1,2,3,4,5,6,6,6,66,7,8,9,10,11,1,1,1,1,1,14,15});
}
public static void oddEvenSort(int[] arr)
{
int temp;
for(int i = 0, j = arr.length-1; i < j;)
{
if(arr[j]%2 == 1)
{
if(arr[i]%2 == 0)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
else
{
i++;
}
}
else
{
if(arr[i]%2 == 0)
{
j--;
}
else
{
i++;
j--;
}
}
}
for(int i : arr)
{
System.out.print(i + ",");
}
}
}
分享到:
相关推荐
运用mpi实现奇偶排序,在不同的处理器之间通过消息传递完成奇偶index的数的交换,实现最终的数列排序
整数奇偶排序(信息学奥赛一本通-T1181).rar
利用mpi进行奇偶排序的实现,有较好的性能和可扩展性
代码稍微有点儿缺陷,默认是10个数据,用5个进程进行排序。所以其中的比较函数写死了,大家可以自己重新改一下这里。
MPICH2+VC++6.0开发,内含奇偶并行排序源代码及EXE可运行程序。
C语言奇偶排序算法 奇偶排序,或奇偶换位排序,或砖排序,是一种相对简单的排序算法,最初发明用于有本地互连的并行计算。这是与冒泡排序特点类似的一种比较排序。该算法中,通过比较数组中相邻的(奇-偶)位置数字...
=====第2题:奇偶排序(一)===== 总时间限制:1000ms内存限制:65536kB描述输入十个整数,将十个整数按升序排列输出,并且奇数在前,偶数在后。输入输入十个整数输出按照奇偶排序好的十个整数 代码如下:#include #...
主要介绍了java数据结构与算法之奇偶排序算法,较为详细的分析了奇偶算法的原理并结合完整示例形式给出了实现技巧,需要的朋友可以参考下
按奇偶排序数组给定一个非负整数数组 A,返回一个数组,在该数组中, A 的所有偶数元素之后跟着所有奇数元素。示例:输入:[3,1,2,4]输出:[2,4,3,1
信息学奥赛一本通代码1181:整数奇偶排序
c语言面试题 c语言面试题之双指针按奇偶排序数组
按奇偶排序数组II一、LeetCode题解瞧一瞧~博健的LeetCode题解:Gitbook版本传送门博健的LeetCode题解:CSDN传送门有趣的CSS:G
设 A[]是由非 0 整数构成的数组,要求设计一个算法重新排列数组 A[]中的数,使得奇数 都排在偶数的前面。要求该算法的时间复杂度为 O(n),空间复杂度为 O(1)。
主要介绍了奇偶排序算法及Java数组的实现,奇偶排序的时间复杂度为O(N^2),需要的朋友可以参考下
922. 按奇偶排序数组 II方法:指向各自集合的双指针偶数下标的元素们相当于一个集合,奇数下标的元素们相当于另一个集合指针 i 指向下标为偶数的元素指针 j
有一个顺序表L,假设元素类型为整型。设计一个算法,将所有奇数移动到偶数的前面。请分析算法的时间复杂度和空间复杂度。
主要介绍了java交换排序之奇偶排序实现方法,实例分析了奇偶排序的原理与具体实现技巧,非常具有实用价值,需要的朋友可以参考下
汇编语言