当前位置:首页 > 开发 > 编程语言 > Java > 正文

java-54- 调整数组顺序使奇数位于偶数前面

发表于: 2012-03-06   作者:bylijinnan   来源:转载   浏览:
摘要: import java.util.Arrays; import java.util.Random; import ljn.help.Helper; public class OddBeforeEven { /** * Q 54 调整数组顺序使奇数位于偶数前面 * 输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半
import java.util.Arrays;
import java.util.Random;

import ljn.help.Helper;


public class OddBeforeEven {

	/**
	 * Q 54 调整数组顺序使奇数位于偶数前面
	 * 输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
	 * update at 2012-04-20:
	 * "quickSort" is O(nlgn).So it does not work
	 * Now we trade space for time.
	 * Create another array which has the same length as the array to be sorted.
	 * Odd number is inserted from front,Even number from tail.
	 */
	public static void main(String[] args) {

		int[] x=new int[10];
		for(int i=0;i<10;i++){
			x[i]=i;
		}
		System.out.println(Arrays.toString(x));
		sort2(x);
		System.out.println(Arrays.toString(x));
		System.out.println("================================");
		rearrange(x);
		System.out.println(Arrays.toString(x));
		sort(x);
		System.out.println(Arrays.toString(x));
	}

	//O(n)--Odd number is inserted from front,Even number from tail.
	public static void sort(int[] x){
		if(x==null||x.length==0){
			return;
		}
		int len=x.length;
		int[] tmp=new int[len];
		int oddPos=0;
		int evenPos=len-1;
		for(int i=0;i<len;i++){
			if(!isEven(x[i])){
				tmp[oddPos++]=x[i];
			}else{
				tmp[evenPos--]=x[i];
			}
		}
		System.arraycopy(tmp, 0, x, 0, len);
	}
	
	//O(nlgn)--like Quick Sort.Find a even from the beginning and a odd from the last.Swap them.
	public static void sort2(int[] x){
		if(x==null||x.length==0){
			return;
		}
		int len=x.length;
		int i=0;
		int j=len-1;
		while(i<j){
			if(!isEven(x[i])){
				i++;
				continue;
			}
			if(isEven(x[j])){
				j--;
				continue;
			}
			if(isEven(x[i])&&!isEven(x[j])){
				Helper.swap(x,i,j);
			}
			
		}
	}
	public static boolean isEven(int x){
		return (x&1)==0;
	}
/*
20120423 update
1. for i:=1 to n do swap(a[i], a[random(1,n)]);  // 凑合,但不是真正随机
2. for i:=1 to n do swap(a[i], a[random(i,n)]);   // 真正的随机算法
其中,random(a,b)函数用于返回一个从a到b(包括a和b)的随机整数。
*/
	public static void rearrange(int[] x){
		int len=x.length;
		for(int i=0;i<len;i++){
			int j=new Random().nextInt(len);
			Helper.swap(x, i, j);
		}
	}
}

java-54- 调整数组顺序使奇数位于偶数前面

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
题目: 输入一个证书数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分
一、题目:调整数组顺序使奇数位于偶数前面 题目:输入一个整数数组,实现一个函数来调整该数组中数
案例 数组内容:3 4 4 6 8 2 1 1 1 调换奇偶:3 1 1 1 8 2 4 4 6 思路 源于快速排序 方式1 参考代码
/* *Copyright (c) 2015, 烟台大学计算机与控制工程学院 *All rights reserved *作者:李宗政 *完成
为了让表格中的行更加突出,条理更加清晰,我们可以对其中的奇数或者偶数行添加背景色 <!doctype
今天呢,由泡泡鱼工作室发布的微信公共号“硬件为王”(微信号:king_hardware)正式上线啦,关注有
思路分析: 类似快速排序的处理。可以用两个指针分别指向数组的头和尾,头指针正向遍历数组,找到第
You are given a function calcDifference which takes in the root pointer of a binary tree as i
程序代码 #include <stdio.h> #include <stdlib.h> void main() { int odd = 0;//奇数
MyEclipse的项目是按照项目名的字母顺序排列的,无法调整。 比如,我现在在进行Photo项目的工作,位
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号