数组分区—荷兰国旗问题?

给定一个数组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
分享
二维码
< <上一篇
 

)">
下一篇>>