Algorithm(一)荷兰国旗问题
一、经典题目
给定一个数组arr,和一个数num,请把小于等于num的数放在数
组的左边,大于num的数放在数组的右边。
要求额外空间复杂度O(1),时间复杂度O(N)
分析: 总体的思想就是小于num的数推着大于num的数向右走,如果当前数小于num,则直接跳下一个数,同时小于的范围扩大一位,如果是大于则是直接跳下一位,知道遇见小于num的数,在和小于范围的下一个数交换
代码:
public class NetherlandsFlag1 {
public static void main(String[] args) {
//给定一个数组和一个num 小于num放左边,大于num放右边
int[] arr = {3,5,1,67,23,18,88};
int num = 20;
changeArr(arr,num);
//拍序打印数据
for (int i : arr) {
System.out.print(i+" ");
}
}
private static void changeArr(int[] arr, int num) {
//定义左边界
int less = -1;
//定义右边界
int more = arr.length;
//定义一个指针
int cur = 0;
//cur小于进入循环
while (cur<more){
if (arr[cur]<num){
//cur下移,并less扩容一位
swap(arr,++less,cur++);
}else{
cur++;
}
}
}
//两个数交换
private static void swap(int[] arr,int i,int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
荷兰国旗问题:
给定一个数组arr,和一个数num,请把小于num的数放在数组的
左边,等于num的数放在数组的中间,大于num的数放在数组的
右边。
要求额外空间复杂度O(1),时间复杂度O(N)
分析:
1.首先是起始的位置,less-1 和more+1这个两个边界
2、定义一个cur变量,用于移动
3、如果cur=num则是cur指针直接下移
4、如果cur<num 则cur指向的数与小于位置的下一个数交换,小于位置扩容一位
5、如果cur>num 则cur指向的数与大于位置的下一个数据交换,大于位置扩容,交换过来的数继续与num判断
6、如果cur与more相遇则是排列完毕
代码:
package com.weiwei.basic_class_01;
public class NetherlandsFlag {
public static int[] partition(int[] arr, int l, int r, int num) {
//左边的小于num的指针
int less = l - 1;
//右边的大于num的指针
int more = r + 1;
//定义一个指针,用于向下移动
int cur = l;
//more为大于num的右边界
//进入循环的必要条件,cur和more不能撞上
while (cur < more) {
if (arr[cur] < num) {
//如果当前位置的数小于num,则less的下一个位置与cur数交换,cur数下移一位
swap(arr, ++less, cur++);
} else if (arr[cur] > num) {
//--more大于的前一个位置的数与cur交换,然后继续判断cur与num的值
swap(arr, --more, cur);
} else {//==num
cur++;
}
}
//等于区域的左边界和等于区域的右边界
return new int[] { less + 1, more - 1 };
}
// for test
//交换两个数
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
//进行对数器验证
// for test
public static int[] generateArray() {
int[] arr = new int[10];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 3);
}
return arr;
}
// for test
public static void printArray(int[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int[] test = generateArray();
printArray(test);
int[] res = partition(test, 0, test.length - 1, 1);
printArray(test);
System.out.println(res[0]);
System.out.println(res[1]);
}
}
这是快速排序学习的基础,非常重要