荷兰国旗问题

问题描述:给定一个数组arr,和一个数num,请把小于num的数放在数组的 左边,等于num的数放在数组的中间,大于num的数放在数组的 右边。 要求额外空间复杂度O(1),时间复杂度O(N)

问题分析:这部分其实和快排中的partition部分很相似,其思想就是将任意一个数组分成三部分,分别是小于 等于 大于 某个num的数组

public class code_08_NetherlandsFlag {
    public static int[] partition(int[] arr, int l ,int r ,int num){
        int less = l - 1;
        int more = r + 1;

        int index = l;
        while (index < more)
        {
            if(arr[index] < num){
                swap(arr ,++less,index++ );
            }
            else if(arr[index] > num)
            {
                swap(arr ,--more,index );
            }
            else{
                index ++;
            }
        }
        return new int[] {less + 1 ,more -1 };
    }

    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

 

上一篇:2021年广州市西关外国语学校中考三模英语试题


下一篇:【Rust日报】 2019-04-24:Rust 2019 Roadmap