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();

    }

}