leetcode-01荷兰国旗
给定一个数组arr,和一个数num,请把小于num的数放在数组的 左边,等于num的数放在数组的中间,大于num的数放在数组的 右边。要求额外空间复杂度O(1),时间复杂度O(N)。
注:快排的改进版,快排的时间复杂度是,
空间复杂度:
package cn.itcats.test;
import org.junit.Test;
/**
*荷兰国旗问题,使用的是两个指针划分两个区域 less 和 more 指针
*/
public class Flag {
public int[] Flag(int[] arr, int num, int L, int R) {
if (arr == null && arr.length < 1) {
return null;
}
int less = L - 1;
int more = R + 1;
while (L < more) {
if (arr[L] < num) {
swap(arr,++less,L++);
}else if(arr[L] > num){
swap(arr,--more,L);
}else {
L++;
}
}
return new int[] {less + 1,more - 1};
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
@Test
public void flagTest() {
int num = 5;
int[] arr = { 4, 5, 3, 7, 6, 8, 0, 5 };
Flag(arr, num, 0, arr.length - 1);
for (int i : arr) {
System.out.print(i + " ");
}
}
}