数组分区—荷兰国旗问题?
给定一个数组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
}
}
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
二维码