问题描述:给定一个数组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; } }