算法-调整数组顺序使奇数位于偶数前面

短命女 2022-04-23 03:18 155阅读 0赞

输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求时间复杂度为O(n)

/**
     * 调整数组顺序使奇数位于偶数前面
     *
     * 输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，
     * 所有偶数位于数组的后半部分。要求时间复杂度为O(n)
     */
    public class OddHead {
    
        /**
         * 方案一
         * 自左向右逐个遍历
         * 效率低下
         *
         * @param nums
         * @return
         */
        public static int[] orderx(int[] nums) {
            if(null == nums || nums.length < 2) {return nums;}
    
            for (int i = 0, j = nums.length - 1; i < nums.length && i < j; i++) {
                int num = nums[i];
                if(num % 2 == 0) {
                    //是偶数
                    int maxOddIndex = getEvenIndex(nums, i, j);
                    if(maxOddIndex < 0){
                        break;
                    }else{
                        nums[i] = nums[maxOddIndex];
                        nums[maxOddIndex] = num;
                    }
                }else{
                    //是奇数
                    continue;
                }
            }
    
            return nums;
        }
    
        //方案二
        //新建一个同长度的数组，从两端向中间转移数据
    
        /**
         * 方案三
         * 基于方案二，但不新建数组
         * 设置左右两个指针，i表示最左侧的一个偶数所在的索引，j表示最右侧的一个奇数所在的索引，
         * 两个指针从再端向中间交换数据，
         * i从0开始遍历，遇到j时结束；i所在的元素如果是偶数，i++；如果是奇数，则停止查找。
         * j从数组最右端开始遍历，遇到i时结束；j所在的元素如果是奇数，j--；如果是偶数，则停止查找。
         * 把i和j所指的元素对调位置，继续i++,j--下一循环查找需要对调的相距最远的元素。
         *
         * 效率高
         * @param nums
         * @return
         */
        public static int[] orderx2(int[] nums) {
            if (null == nums || nums.length <= 1) {return nums;}
    
            //i,j分别做为前端的奇数指针和后端的偶数指针
            int i = 0, j = nums.length - 1;
            while (i < j) {
                int num = nums[i];
                if(isOdd(num)) {
                    j = getEvenIndex(nums, i, j);
                    if(j < 0 || j < i) {
                        //已经遍历完所有的元素
                        break;
                    }
                    //把找到位于j的奇数和位于i的偶数交换位置
                    nums[i] = nums[j];
                    nums[j] = num;
                    j--;  //每使用一次偶数下标，就需要偶数下标自减一次
                }
                i++;  //奇数下标自增
            }
    
            return nums;
        }
    
        /**
         * 用位操作判断是否为偶数
         * @return
         */
        private static boolean isOdd(int n){
            return (n&1)==0;
        }
    
    
        /**
         * 递归找最大的奇数位
         *
         * @param nums
         * @param i
         * @param j
         * @return
         */
        private static int getEvenIndex(int[] nums, int i, int j) {
           if(i >= j) {return -1;}
    
           if(!isOdd(nums[j])) {
               //是奇数
               return j;
           }else{
               j--;
               return getEvenIndex(nums, i, j);
           }
    
        }
    
        public static void main(String[] args) {
            OddHead oddHead = new OddHead();
            int[] nums = ArrayUtil.getArray(20, 10);//new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 19, 21, 23};
    //        oddHead.orderx(nums);
            int[] numsNew = orderx2(nums);
            ArrayUtil.print(numsNew);
    
        }
    }

数据工具类

/**
     * 生成随机的，无序的整数数组
     */
    public class ArrayUtil {
    
        /**
         * 生成一个元素不重复的整型数组，且数组的最大值是max，长度是n
         *
         * @param max 最大值
         * @param n   数组的长度
         * @return
         */
        public static int[] getArray(int max, int n) {
            if(max < 1 || n < 1) return new int[]{};
    
            int[] array = new int[n];
    
            Set<Integer> set = new HashSet<Integer>();
    
            for (int i = 0; i < n; i++) {
                int random = getNextInt(set, max);
                set.add(random);
                array[i] = random;
            }
    
            //打印数组
            print(array);
    
            return array;
        }
    
    
        /**
         * 随机生成不重复的数字
         *
         * @param set
         * @param max
         * @return
         */
        private static int getNextInt(Set<Integer> set, int max) {
            if(max < 0) {return 0;}
    
            int random = new Random().nextInt(max);
            if(null == set || set.isEmpty()) {return random;}
    
            if(set.contains(Integer.valueOf(random))) {
                return getNextInt(set, max);
            }else{
                return random;
            }
        }
    
        /**
         * 打印数组
         * @param nums
         */
        public static void print(int[] nums) {
            if(null == nums) {return ;}
            for (int i = 0; i < nums.length; i++) {
                System.out.print(nums[i]+",");
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
            ArrayUtil.getArray(10, 8);
            ArrayUtil.getArray(20, 10);
        }
    
    }