给定一个数组arr,和一个整数num,将数组分为三段,[< | = | >]。把小于num的数放在数组左边,等于num的数放在中间,大于num的数放在右边,小于部分和大于部分可以无序。——经典的荷兰国旗问题。
但是以下代码实现方式是以数组最后一个元素作为num,所以本题就是一个经典的荷兰国旗划分三色问题
package com.harrison.class03; public class Code04_Netherlands { public static int[] netherlands(int[] arr, int L, int R) { if (L > R) { return new int[] { -1, -1 }; } if (L == R) { return new int[] { L, R }; } int less = L - 1; int more = R; int i = L; while (i < more) { if (arr[i] == arr[R]) { i++; } else if (arr[i] < arr[R]) { swap(arr, i++, ++less); } else { swap(arr, i, --more); } // L...less less+1...more-1 more...R-1 R // L...less less+1..........more more+1...R swap(arr, more, R); } return new int[] { less + 1, more }; } public static void swap(int[] arr, int i, int j) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } public static void main(String[] args) { int[] arr= {9,32,3,4,-3,4,3,90,-3,9}; int[] ans=netherlands(arr, 0, arr.length-1); for(int i=0; i<ans.length; i++) { System.out.print(ans[i]+" "); } // -3 -3 3 3 4 4 | 9 9 | 32 90 // 6,7 } }