题目一:
给定一个数组arr,和一个数num,请把小于等于num的数放在数 组的左边,大于num的数放在数组的右边。 要求额外空间复杂度O(1),时间复杂度O(N) 问题二(荷兰国旗问题) 给定一个数组arr,和一个数num,请把小于num的数放在数组的 左边,等于num的数放在数组的中间,大于num的数放在数组的 右边。 要求额外空间复杂度O(1),时间复杂度O(N)
/**
* 问题:(荷兰国旗问题)
* 给定一个数组arr,和一个数num,请把小于num的数放在数组的 左边,等于num的数放在数组的中间,大于num的数放在数组的 右边。
* 要求额外空间复杂度O(1),时间复杂度O(N)
*/
public class NetherLandsFlag {
public static int[] partition(int [] arr,int L,int R,int num){
int less=L-1;
int more=R+1;
int cur=L;
while (cur<more){
if (arr[cur]<num){
swap(arr,++less,cur++);
}else if(arr[cur]>num){
swap(arr,--more,cur);
}else {
cur++;
}
}
return arr;
}
private static void swap(int[] arr, int i, int j) {
arr[i]=arr[i]^arr[j];
arr[j]=arr[i]^arr[j];
arr[i]=arr[i]^arr[j];
}
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;
}
public static void main(String[] args) {
int [] arr=generateArray();
int[] res=partition(arr,0,arr.length-1,2);
System.out.println(Arrays.toString(res));
}
}
题目二:
随机快速排序的细节和复杂度分析 可以用荷兰国旗问题来改进快速排序 时间复杂度O(N*logN),额外空间复杂度O(logN)
/**
* 快排
*/
public class QuickSort {
public static void quickSort(int [] arr){
if (arr==null || arr.length<2){
return;
}
quickSort(arr,0,arr.length-1);
}
private static void quickSort(int[] arr, int L, int R) {
if (L<R){
int [] p=partition(arr,L,R);
quickSort(arr,L,p[0]-1);
quickSort(arr,p[1]+1,R);
}
}
private static int[] partition(int[] arr, int L, int R) {
int less=L-1;
int more=R;
int cur=L;
while (cur<more){
if (arr[cur] < arr[R]) {
swap(arr,++less,cur++);
}else if(arr[cur]> arr[R]){
swap(arr,--more,cur);
}else {
cur++;
}
}
swap(arr,more,R);
return new int[]{less+1,more};
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args) {
int [] arr={12,10,4,10,10,8,9,10};
quickSort(arr);
System.out.println(Arrays.toString(arr));
}
}
题目三 堆排序的细节和复杂度分析 时间复杂度O(N*logN),额外空间复杂度O(1) 堆结构非常重要
1,堆结构的heapInsert与heapify 2,堆结构的增大和减少 3,如果只是建立堆的过程,时间复杂度为O(N) 4,优先级队列结构,就是堆结构
/**
* 堆排
*/
public class HeapSort {
public static void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
int size = arr.length;
swap(arr, 0, --size);
while (size > 0) {
heapify(arr, 0, size);
swap(arr, 0, --size);
}
}
public static void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
public static void heapify(int[] arr, int index, int size) {
int left = index * 2 + 1;
while (left < size) {
int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
largest = arr[largest] > arr[index] ? largest : index;
if (largest == index) {
break;
}
swap(arr, largest, index);
index = largest;
left = index * 2 + 1;
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args) {
int []arr={1,34,4,5,76,8,9};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
}
有关排序问题的补充:
1,归并排序的额外空间复杂度可以变成O(1),但是非常难,不 需要掌握,可以搜“归并排序 内部缓存法” 2,快速排序可以做到稳定性问题,但是非常难,不需要掌握, 可以搜“01 stable sort” 3,有一道题目,是奇数放在数组左边,偶数放在数组右边,还 要求原始的相对次序不变,碰到这个问题,可以怼面试官。面试官非良人。
参考:牛客算法进阶