算法——荷兰国旗（数组分区）

2022-3-5 diaba 算法 

package com.jiucaiyuan.net.algrithm.sort;

/**
 * 问题（荷兰国旗问题）：给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，
 * 大于num的数放在数组的右边，要求额外空间复杂度O(1)，时间复杂度O(N)
 *
 * Created by jiucaiyuan on 2022/3/5.
 */
public class SplitArrayHeLan {
    /**
     * less为小的区域最右侧
     * more为大的区域最左侧
     * i是扫描整个数组
     * @param arr
     * @param num
     * @return
     */
    public static int[] splitArray(int[] arr,int num){
        if(arr == null || arr.length < 2){
            return new int[]{0,0};
        }
        int less = -1;
        int more = arr.length;
        for(int i=0;i<arr.length && i<more;){
            if(arr[i]<num){
                swap(arr,++less,i++);
            }else if(arr[i]>num){
                swap(arr,i,--more);
            }else{
                i++;
            }
        }
        return new int[]{less,more};

    }

    /**
     * 交换两个不相等的数，如果相等，会都变成0
     * @param arr
     * @param l
     * @param r
     */
    private static void swap(int[] arr,int l,int r){
        if(l==r){
            return;
        }
        //交换两个不同数
        arr[l] = arr[l]^arr[r];
        arr[r] = arr[l]^arr[r];
        arr[l] = arr[l]^arr[r];
    }

    public static void main(String[] args){
        int[] arr = {12,5,3,7,3,8,4,3,2,2,6,8,6,0,9,5,3};
//        int[] arr = {5,5,5,5,5};
        print(arr);
        int[] limits = splitArray(arr, 5);
        System.out.println("小区区域上下限="+limits[0]+"-"+limits[1]);
        print(arr);
    }
    private static void print(int[] arr) {
        if(arr == null ){
            return;
        }
        for(int a : arr){
            System.out.print(a+"\t");
        }
        System.out.println();
    }
}

« 算法——字符串转化为32位有符号整数atoi() | 算法——归并法排序»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022