荷兰国旗问题

　

荷兰国旗

问题描述：给定一个k，把比k小的放数组的左边，=k的放中间，>k的放右边。

题解：

就是快排中的partition步骤。

用less指针表示比k小的最后一个元素的位置，more表示比k大的第一个元素的位置。

用cur指针指向当前位置，如果当前元素小于k，直接把它和less+1位置交换，并且less++。由于less以及less以前的必然小于k，所以less+1必然大于等于k（如果<k,只能是cur就在less+1的位置），所以直接交换，cur也右移。

如果>k，那么就和more-1位置元素交换，并且more--。由于more-1位置不知道数是多大，所以cur不能动，需要再次比较。

package sort;

import java.util.*;

public class NetherlandFlag {
	public static int[] partition(int[] arr,int L,int R,int num) {
		int cur = L;
		int less = L-1;
		int more = R+1;
		while(cur<more) { //这里不是小于等于
			if(arr[cur]<num) {
				swap(arr,cur++,++less);
			} else if(arr[cur]==num) {
				cur++;
			} else if(arr[cur]>num){
				swap(arr,cur,--more); //这里就是cur，不是cur++，因为交换回来的数不知道是多大
			}
		}
		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;
	}
	
	public static void main(String args[]) {
		scanner in = new Scanner(System.in);
		int n,k;
		n = in.nextint();
		k = in.nextInt();
		int[] a = new int[n];
		for(int i=0;i<n;i++)
			a[i] = in.nextInt();
		int[] b=partition(a,0,n-1,k);
		for(int i=0;i<2;i++)
			System.out.println(b[i]);
	}
}

相关阅读

python socket.error: [Errno 10054] 远程主机强迫关

python socket.error: [Errno 10054] 远程主机强迫关闭了一个现有的连接。问题解决方案：前几天使用python读取网页

护士英文面试常见问题

Why did you choose nursing?Why do you want to work for us?What courses did you like best/least? Why?What qualities do yo

用微信登录很简单？这些问题你考虑过吗？

用户有时会因注册、登录麻烦，而放弃使用产品，这时如果能够用微信一键登录，将会有效降低用户流失。不过微信登录中也有这些坑，注意别踩

解决找不到mfc100u.dll问题

当运行一个更新的应用程序或安装较新的应用程序时，往往会出现“找不到动态链接库mfc100u.dll”的错误报告。除了.dll文件丢失，没有

Debug Assertion Failed 问题怎么解决

分享一下我老师大神的人工智能教程！零基础，通俗易懂！http://blog.csdn.net/jiangjunshow也欢迎大家转载本篇文章。分享知识，造福人民，