B站课程连接
排序 交换数组中的两个数//常规方法
public static void swap1(int[]arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//用位运算,执行速度更快,少申请一个变量
public static void swap2(int[] arr,int i,int j){
if(arr[i] == arr[j]){//如果arr[i]和arr[j]指向同一块内存会出错,所以干脆不交换
return;
}
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[j] ^ arr[i];
arr[i] = arr[i] ^ arr[j];
}
生成随机数组
public static int[] generateRandomArray(int maxSize,int maxValue){
int[] arr = new int[(int)((maxSize + 1) * Math.random())];//随机长度
for (int i = 0;i < arr.length;i++) {
//一个随机数减去另一个随机数,生成一个[-maxValue,maxValue]的随机数
arr[i] = (int)((maxValue+1)*Math.random())
- (int)((maxValue+1)*Math.random());
}
return arr;
}
冒泡排序
public static void bubbleSort(int[] arr){
if(arr == null || arr.length <2){
return;
}
for(int i = 1; i < arr.length; i++){
for(int j = 0; j < arr.length - i; j++){
if (arr[j + 1] < arr[j]) {
swap(arr,j + 1,j);
}
}
}
}
选择排序
public static void selectSort(int[] arr){
if(arr == null || arr.length <2){
return;
}
for(int i = 0; i < arr.length - 1; i++){
int minIndex = i;
for(int j = i + 1; j < arr.length; j++){
if(arr[minIndex] > arr[j]){
minIndex = j;
}
}
swap(arr,minIndex,i);
}
}
插入排序
public static void insertSort(int[] arr){
if(arr == null || arr.length <2){
return;
}
for(int i = 1;i < arr.length;i++){
for(int j = i; j > 0 && arr[j] < arr[j-1];j--){
swap(arr,j,j - 1);
}
}
}
归并排序
merge:前半部分有序,后半部分有序,让整体变有序
public static void merge(int[] arr,int L,int M,int R){
int[] help = new int[R - L + 1];
int p1 = L;
int p2 = M + 1;
int i = 0;
while(p1 <= M && p2 <= R){
help[i++] = arr[p1] <= arr[p2]? arr[p1++]:arr[p2++];
}
while(p1 <= M){
help[i++] = arr[p1++];
}
while(p2 <= R){
help[i++] = arr[p2++];
}
for(i = 0;i < help.length;i++){
arr[L + i] = help[i];
}
}
递归实现
public void mergesort(int[] arr,int L,int R){
if(L == R){
return;
}
int mid = L + ((R - L) >> 1);
mergesort(arr,L,mid);
mergesort(arr,mid +1,R);
merge(arr,L,mid,R);
}
非递归
public static void mergesort02(int[] arr){
if(arr == null || arr.length < 2){
return;
}
int mergeSize = 1;
int N = arr.length;
while(mergeSize < N){
int L = 0;
while(L < N){
int M = L + mergeSize;
if(M >= N){
break;
}
int R =Math.min(L + mergeSize,N - 1);
merge(arr,L,M,R);
L = R + 1;
}
if(mergeSize > (N >> 1)){
break;
}
mergeSize <<= 1;
}
}
快速排序
Partition
给一个数,把数组中小于等于这个数的数放左边,其他放右边
public static int partition(int[] arr,int L,int R){
if(L > R){
return -1;
}
if(L == R){
return L;
}
int less = L - 1;
int more = R;
int index = L;
while(L < R){
if(arr[index] == arr[R]){
index++;
}else if(arr[index] < arr[R]){
swap(arr,index++,++less);
}else{
swap(arr,index,--more);
}
}
swap(arr,more,R);
return more;
}
public static void swap(int[] arr,int i,int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
荷兰国旗问题
给一个数,把数组中小于这个数的数放左边,等于放中间,大于放右边
public static int partition(int[] arr,int L,int R){
if(L > R){
return -1;
}
if(L == R){
return L;
}
int less = L - 1;
int more = R;
int index = L;
while(L < R){
if(arr[index] == arr[R]){
index++;
}else if(arr[index] < arr[R]){
swap(arr,index++,++less);
}else{
swap(arr,index,--more);
}
}
swap(arr,more,R);
return more;
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
快排1.0
用partition
public static void quicksort01(int[] arr,int L,int R){
if(L >= R){
return;
}
int M = partition(arr,L,R);
quicksort01(arr,L,M);
quicksort01(arr,M + 1,R);
}
快排2.0
用荷兰国旗
public static void quicksort02(int[] arr, int L, int R) {
if (L >= R) {
return;
}
int[] equalArea = netherlandsFlag(arr, L, R);
quicksort02(arr, L, equalArea[0] - 1);
quicksort02(arr, equalArea[1] + 1, R);
}
快排3.0(随机快排)
在2.0的基础上加随机,达到s时间复杂度O(N*logN)
public static void quicksort03(int[] arr,int L,int R){
if (L <= R){
return;
}
swap(arr,L + (int) (Math.random() * (R - L + 1)),R);
int[] equalArea = NetherlandsFlag.netherlandsFlag(arr,L,R);
quicksort03(arr,L,equalArea[0] - 1);
quicksort03(arr,equalArea[1] + 1,R);
}
public static void swap(int[]arr,int i,int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
结论:每种情况出现是等概率时,所有情况的时间复杂度的期望是O(N*logN)
堆排序跳转
几乎有序的数组
桶排序不基于比较的排序
应用范围很有限,如果数据有变动,算法很可能要大规模重写
计数排序
public static void countSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
int max = Integer.MIN_VALUE;
//找出最大值
for(int i = 0; i < arr.length; i++){
max = Math.max(max,arr[i]);
}
//准备一个max + 1 个桶
int[] bucket = new int[max + 1];
//计数
for(int i = 0; i < arr.length; i++){
bucket[arr[i]]++;
}
int i = 0;
//倒出
for(int j = 0; j < bucket.length; j++){
while(bucket[j]-- > 0){
arr[i++] = j;
}
}
}
基数排序
public class RadixSort {
//只能处理非负值
public static void radixSort(int[] arr){
if(arr == null || arr.length < 2){
return;
}
radixSort(arr,0,arr.length - 1,maxBits(arr));
}
public static int maxBits(int[]arr){
int max = Integer.MIN_VALUE;
for(int i = 0;i < arr.length; i++){
max = Math.max(max,arr[i]);
}
int res = 0;
while(max != 0){
res++;
max /= 10;
}
return res;
}
public static void radixSort(int[] arr, int L, int R, int digit){
final int radix = 10;//十进制
int i = 0, j = 0;
int[] help = new int[R - L +1];//等长数组
for(int d = 1; d <= digit; d++) {//从个位开始,每一位入桶
int[] count = new int[radix];
//count
for(i = L;i <= R; i++){
j = getDigit(arr[i], d);
count[j]++;
}
//count'
for(i = 1; i < radix; i++){
count[i] += count[i - 1];
}
//help
for(i = R; i >= L; i--){
j = getDigit(arr[i], d);
help[count[j] - 1] = arr[i];
count[j]--;
}
//倒回去
for(i = L,j =0; i <= R; i++,j++){
arr[i] = help[j];
}
}
}
public static int getDigit(int num, int digit){
int bits = 0;
int cloneOfNum = num;
while(cloneOfNum != 0){
bits++;
cloneOfNum /= 10;
}
if(digit > bits || digit <= 0){
return 0;
}
return (num / (int)Math.pow(10,digit - 1)) % 10;
}
}
总结
| 基于比较 | 时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 选择排序 | O(N^2) | O(1) | 无 |
| 冒泡排序 | O(N^2) | O(1) | 有 |
| 插入排序 | O(N^2) | O(1) | 有 |
| 归并排序 | O(N*logN) | O(N) | 有 |
| 随即快排 | O(N*logN) | O(logN) | 无 |
| 堆排序 | O(N*logN) | O(1) | 无 |
| 不基于比较 | |||
| 计数排序 | O(N) | O(M) | 有 |
| 基数排序 | O(N) | O(N) | 有 |
-
比时间,选快排
-
比空间,选堆排
-
比稳定性,选归并
public static boolean dichotomySearch(int[] arr,int target){
if(arr == null || arr.length ==0){
return false;
}
int L = 0;
int R = arr.length-1;
int mid = 0;
while(L < R){
mid = L + ((R - L) >> 1);
if(arr[mid] == target){
return true;
}
else if(arr[mid] > target){
R = mid - 1;
}
else {
L = mid + 1;
}
}
return arr[L] == target;
}
有序数组中,找>=某个数最左侧的位置
public static int firstLeft(int[]arr,int target){
int L = 0;
int R = arr.length -1;
int mid = 0;
int res = -1;
while(L <= R){
mid = L + ((R - L) >> 1);
if(arr[mid] >= target){
res = mid;
R = mid -1;
}
else{
L = mid + 1;
}
}
return res;
}
局部最小值
无序数组中,任何相邻的两个数都不相等,找局部最小值,局部最小值定义为既小于左边数,也小于右边数。
public static int localMin(int[] arr){
if(arr == null || arr.length == 0){
return -1;
}
int L = 0;
int R = arr.length - 1;
//先看开头和末尾是不是局部最小
if(arr.length == 1 || arr[0] < arr[1]){
return 0;
}
if(arr[R] < arr[R - 1]){
return R - 1;
}
//如果开头和末尾没有局部最小,则中间必定存在局部最小
//按这种思路二分,总会找到
while(L < R){
int mid = L + ((R - L) >> 1);
if(arr[mid] > arr[mid + 1]){
L = mid + 1;
}else if(arr[mid] > arr[mid -1]){
R = mid - 1;
}else{
return mid;
}
}
return -1;
//这里return什么都可以,因为不可能执行到这一步,上面那个while必找到局部最小
//任何相邻不相等的数组必存在局部最小
}
认识异或运算
- 0 ^ N == N N ^ N == 0
- 异或运算满足交换律和结合律
- 用无进位相加来理解异或运算
public static void swap2(int[] arr,int i,int j){
if(arr[i] == arr[j]){//如果arr[i]和arr[j]指向同一块内存会出错,所以干脆不交换
return;
}
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[j] ^ arr[i];
arr[i] = arr[i] ^ arr[j];
}
数组中只有一种数出现了奇数次,打印这种数
public static void onlyOne(int[] arr){
if(arr == null){
return;
}
if(arr.length < 2){
System.out.println(arr[0]);
return;
}
int ans = arr[0];
for(int i = 1;i < arr.length;i++){
ans ^= arr[i];
}
System.out.println(ans);
}
提取最右侧的1
举例:把二进制数0111100变成0000100
取反加1再相与
N&((~N)+1)
public static int farRightOne(int num){
return num & ((~num)+1);
}
数组中有两种数出现了奇数次,打印这两种数
public static void twoOddTimes(int[] arr){
int eor = arr[0];
for(int i = 1;i < arr.length;i++){
eor ^= arr[i];
}
//假设答案是a和b,全部相与,得到a^b的值
//eor = a ^ b
//eor != 0
//eor必然有一个位置是1
//a和b中必然有一个数某一位是1,但另一个数这一位不是1
int farRightOne = eor & ((~eor)+1);//提取最右侧的1
int eor1 = 0;
//将数组分为某一位是1和0的两组
for(int i = 0;i < arr.length;i++){
if((arr[i] & farRightOne) != 0){//相与不为0说明这一位上是1
eor1 ^= arr[i];
}
}
System.out.println(eor1 + " " + (eor1 ^ eor));
}
数出一个数的二进制形式中有几个1
public static int howManyOnes(int num){
int count = 0;
while(num != 0){
int farRightOne = num & ((~num)+1);
num ^= farRightOne;//每次消去最右侧的1
count ++;
}
return count;
}
链表
单向链表
public class Node {
public int value;
public Node next;
public Node(int data){
value = data;
}
//翻转
public static Node reverseLinkedList(Node head){
Node next = null;
Node last = null;
while(head != null){
next = head.next;
head.next = last;
last = head;
head = next;
}
return last;
}
//删除指定元素
public static Node removeValue(Node head,int num){
while(head != null){
if(head.value != num){
break;
}
head = head.next;
}
Node last = head;
Node cur = head;
while(cur != null){
if(cur.value == num){
last.next = cur.next;
}else{
last = cur;
}
cur = cur.next;
}
return head;
}
}
双向链表
public class DoubleNode双向链表实现队列和栈{ public T value; public DoubleNode next; public DoubleNode last; public DoubleNode(T data){ value = data; } //翻转 public DoubleNode reverseDoubleList(DoubleNode head){ DoubleNode last = null; DoubleNode next = null; while(head != null){ head.next = next; head.next = last; head.last = next; last = head; head = next; } return last; } //删除指定元素 public DoubleNode removeValue(DoubleNode head, T num){ while(head != null){ if(head.value != num){ break; } head = head.next; } DoubleNode last = head; DoubleNode cur = head; DoubleNode next = head.next; while(cur != null){ if(cur.value == num){ last.next = next; next.last = last; } else{ last = cur; } next = cur.next; cur = cur.next; } return head; } }
public class MyNode实现队列{ public DoubleNode H; public DoubleNode T; public void pushFromHead(T data){ DoubleNode newNode = new DoubleNode<>(data); if(H == null){ T = newNode; }else { H.last = newNode; newNode.next = H; } H = newNode; } public void pushFromTail(T data){ DoubleNode newNode = new DoubleNode<>(data); if(T == null){ H = newNode; }else{ T.next = newNode; newNode.last = T; } T = newNode; } public T popFromHead(){ if(H == null){ return null; } DoubleNode popNode = H; if(H == T){ H = null; T = null; }else { H = H.next; H.last = null; popNode.next = null; } return popNode.value; } public T popFromTail(){ if(T == null){ return null; } DoubleNode popNode = T; if(H == T){ H = null; T = null; }else { T = T.last; T.next = null; popNode.last = null; } return popNode.value; } }
public class ListQueue实现栈{ MyNode node; public ListQueue(){ node = new MyNode (); } public void push(T value){ node.pushFromTail(value); } public void pop(){ node.popFromHead(); } }
public class ListStack返回中点{ MyNode node; public ListStack(){ node = new MyNode (); } public void push(T value){ node.pushFromTail(value); } public void pop(){ node.popFromTail(); } }
import java.util.ArrayList;
public class GetMid {
//笔试用Arraylist
//时间复杂度:O(N)
//空间复杂度:O(N)
public static Node getMid01(Node head){
if(head == null){
return null;
}
ArrayList help = new ArrayList<>();
while(head.next != null){
help.add(head);
head = head.next;
}
return help.get((help.size() - 1) / 2);//返回中点或上中点
}
//面试用双指针
//时间复杂度O(N)而且比上面的Arraylist节省一半的时间
//空间复杂度O(1)
//双指针
//中点和上中点
public static Node getMid02(Node head){
if(head == null){
return null;
}
Node f = head;
Node s = head;
while(f.next != null && f.next.next != null){
f = f.next.next;
s = s.next;
}
return s;
}
//中点和下中点
public static Node getMid03(Node head){
if(head == null || head.next == null){
return head;
}
Node f = head;
Node s = head.next;
while(f.next != null && f.next.next != null){
f = f.next.next;
s = s.next;
}
return s;
}
}
是否为回文结构
public class IsPalindrome {
public static boolean isPalindrome(Node head){
if(head == null || head.next == null){
return true;
}
Node help = GetMid.getMid02(head);
Node l = help.next;
Node r = null;
//让后半部分的指针反向指
while(l != null){
r = l.next;
l.next = help;
help = l;
l = r;
}
r = help;
l = head;
boolean res = true;
//对比前半部分和后半部分
while(r != null && l != null){
if(r.value != l.value){
res = false;
break;//不直接return false是因为要把链表还原回去
}
r = r.next;
l = l.next;
}
r = help.next;
help.next = null;
//还原
while(r != null){
l = r.next;
r.next = help;
help = r;
r = l;
}
return res;
}
}
Partition
public static Node listPartition(Node head, int value){
Node lh = null;
Node lt = null;
Node eh = null;
Node et = null;
Node mh = null;
Node mt = null;
Node next = null;
while(head != null){
next = head.next;
head.next = null;
if(head.value < value){
if(lh == null){
lh = head;
}else{
lt.next = head;
}
lt = head;
}else if(head.value == value){
if(eh == null){
eh = head;
}else{
et.next = head;
}
et = head;
}else{
if(mh == null){
mh = head;
}else{
mt.next = head;
}
mt = head;
}
head = next;
}
if(lt != null){
lt.next = eh;
et = et == null ? lt : et;
}
if(et != null){
et.next = mh;
}
return lh != null ? lh : eh != null ? eh : mh;
}
rand克隆
import java.util.HashMap;
public class Node {
int value;
Node next;
Node rand;
public Node(int v){
value = v;
}
}
public class Clone {
//用hashmap
public static Node clone01(Node head){
HashMap hashMap = new HashMap<>();
Node cur = head;
while(cur != null){
hashMap.put(cur,new Node(cur.value));
cur = cur.next;
}
cur = head;
while(cur != null){
hashMap.get(cur).next = hashMap.get(cur.next);
hashMap.get(cur).rand = hashMap.get(cur.rand);
cur = cur.next;
}
return hashMap.get(head);
}
//不用hashmap
public static Node clone02(Node head){
if(head == null){
return null;
}
Node cur = head;
while(cur != null){
Node cloneNode = new Node(cur.value);
cloneNode.next = cur.next;
cur.next = cloneNode;
cur = cloneNode.next;
}
cur = head;
while(cur != null){
cur.next.rand = cur.rand == null ? null : cur.rand.next;
cur = cur.next.next;
}
Node res = head.next;
cur = head;
Node help;
while(cur != null){
help = cur.next;
cur.next = cur.next.next == null ? null : cur.next.next;
help.next = cur.next == null ? null : cur.next.next;
cur = cur.next;
}
return res;
}
}
入环节点
public static Node intersection(Node head){
//节点数小于3返回null
if(head == null || head.next == null || head.next.next == null){
return null;
}
Node s = head.next;
Node f = head.next.next;
while(!s.equals(f)){
//为null说明无环
if(f.next == null || f.next.next == null){
return null;
}
s = s.next;
f = f.next.next;
}
//相遇后f回到head的位置
f = head;
//再次相遇时便是入环节点的位置
while(!s.equals(f)){
f = f.next;
s = s.next;
}
return s;
}
相交节点 数组 固定大小的数组实现队列和栈 实现队列证明:
快指针与慢指针均从X出发,在Z相遇。此时,慢指针行使距离为a+b,快指针为a+b+n(b+c)。所以2*(a+b)=a+b+n*(b+c),推出
a=(n-1)b+nc=(n-1)(b+c)+c;
得到,将此时两指针分别放在起始位置和相遇位置,并以相同速度前进,当一个指针走完距离a时,另一个指针恰好走出 绕环n-1圈加上c的距离。
环形链表第一个入环节点
public class ArrayQueue {
private Object[] arr;
private int size;
private int H;
private int T;
private final int limit =7;
public ArrayQueue(){
arr = new Object[7];
size = 0;
H = 0;
T = 0;
}
public void push(Object value){
if(size == limit){
System.out.println("Queue is full");
return;
}
if(++T >= limit){
T = 0;
}
arr[T] = value;
size++;
}
public Object pop(){
if(size == 0){
System.out.println("Queue is empty");
return null;
}
Object popValue = arr[H];
if(H != T){
if(++H >=limit){
H = 0;
}
}
size--;
return popValue;
}
}
实现栈
public class ArrayStack {
Object[] arr;
int size;
public ArrayStack(){
arr = new Object[7];
size = 0;
}
public void push(Object value){
if(size == 7){
System.out.println("Stack is full");
return;
}
arr[size++] = value;
}
public Object pop(){
if(size == 0){
System.out.println("Stack is empty");
return null;
}
return arr[--size];
}
}
栈
可以返回最小元素的栈
实现一个特殊的栈,再基本功能的基础上,再实现返回栈中最小元素的功能
- pop、push、getMin操作的时间复杂度都是O(1)
- 设计的栈类型可以用现成的栈结构
public class MinStack {
private Stack dataStack;
private Stack minStack;
int min;
public MinStack(){
dataStack = new Stack<>();
minStack = new Stack<>();
}
public void push(int value){
minStack.push(minStack.peek() > value? value:minStack.peek());
dataStack.push(value);
}
public int getMin(){
return minStack.peek();
}
public Object pop(){
minStack.pop();
return dataStack.pop();
}
}
固定大小的数组实现栈
跳转
用栈实现队列public class StackToQueue用队列实现栈{ private Stack pushStack; private Stack popStack; public StackToQueue(){ pushStack = new Stack<>(); popStack = new Stack<>(); } public void push(T value){ pushStack.push(value); } public T pop(){ if(popStack.isEmpty() && pushStack.isEmpty()){ System.out.println("Queue is empty"); return null; }else if(popStack.isEmpty()){ while(!pushStack.isEmpty()){ popStack.push(pushStack.pop()); } } return popStack.pop(); } }
跳转
双向链表实现栈跳转到双向链表
队列 固定大小数组实现队列跳转
用队列实现栈public class QueueToStack用栈实现队列{ LinkedList l1; LinkedList l2; public QueueToStack(){ l1 = new LinkedList<>(); l2 = new LinkedList<>(); } public void push(T value){ if(l2.isEmpty()){ l1.push(value); }else { l2.push(value); } } public T pop(){ if(l1.isEmpty() && l2.isEmpty()){ System.out.println("Stack is empty"); return null; } if(l2.isEmpty()){ for(int i = 0;i < l1.size()-1;i++){ l2.push(l1.pop()); } return l1.pop(); }else { for(int i = 0;i < l2.size()-1;i++){ l1.push(l2.pop()); } return l2.pop(); } } }
跳转
双向链表实现队列跳转到双向链表
递归 Master公式用递归实现数组上下标L到R的最大值形如
T(N) = a * T(N/b) + O(N^d)(其中a、b、d都是常数)
的递归函数,可以直接通过Master公式来确定时间复杂度
如果log(b,a) < d,复杂度为O(N^d)
如果log(b,a) > d,复杂度为O(N^log(b,a))
如果log(b,a) = d,复杂度为O(N^d * logN)
public static int getMax(int[] arr,int L,int R){
if(L == R){
return arr[L];
}
int mid = L + ((R - L) >> 1);
int leftMax = getMax(arr,L,mid);
int rightMax = getMax(arr,mid + 1,R);
return Math.max(leftMax,rightMax);
}
归并排序
跳转
数组小和在一个数组中,一个数左边比它小的数的总和,叫数的小和,数组中所有数的小和,叫数组小和
public int smallSum(int[] arr,int L,int R){
if(L == R){
return 0;
}
int M = L + ((R - L) >> 1);
return smallSum(arr,L,M)
+
smallSum(arr,M + 1,R)
+
merge(arr,L,M,R);
}
public static int merge(int[] arr,int L,int M,int R){
int[] help = new int[R - L + 1];
int i = 0;
int res = 0;
int p1 = L;
int p2 = M + 1;
while(p1 <= M && p2 <= R){
res = arr[p1] < arr[p2]? (R - p2 + 1) * arr[p1]:0;
help[i++] = arr[p1] <= arr[p2]?arr[p1++]:arr[p2++];
}
while(p1 <= M){
help[i++] = arr[p1++];
}
while(p2 <= R){
help[i++] = arr[p2];
}
for(i = 0;i < help.length;i++){
arr[L + i] = help[i];
}
return res;
}
树
堆
大根堆
任何子树最大值都是头结点的值
public class BigHeap {
//heapSize既表示新来的数该放哪,又表示堆大小
int heapSize;
int[] heap;
private final int limit;
public BigHeap(int limit){
heapSize = 0;
heap = new int[limit];
this.limit = limit;
}
public boolean isEmpty(){
return heapSize == 0;
}
public boolean isFull(){
return heapSize == limit;
}
public void push(int value){
if(isFull()){
throw new RuntimeException("heap is full");
}
heap[heapSize] = value;
heapInsert(heap,heapSize++);
}
private void heapInsert(int[] arr,int index){
while(arr[index] > arr[(index - 1) / 2]){
swap(arr,index,(index - 1) / 2);
index = (index - 1) / 2;
}
}
private void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public int pop(){
int ans = heap[0];
//第一个数和最后一个数交换,
swap(heap,0,--heapSize);
heapify(heap,0,heapSize);
return ans;
}
private void heapify(int[] arr,int index,int heapSize){
//左孩子下标
int left = index * 2 + 1;
//不越界时
while(left < heapSize){
//获取较大孩子的下标
int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
//获取子树中最大值的下标
largest = arr[largest] > arr[index] ? largest : index;
//如果最大值就是自己,break
if(largest == index){
break;
}
//自己和最大值交换
swap(arr,index,largest);
//下沉
index = largest;
//左孩子下标
left = index * 2 + 1;
}
}
}
堆排序
在时间复杂度O(N*logN)的情况下,额外空间复杂度可达到O(1)
public class HeapSort {
public void heapSort1(int[] arr){
//从后往前heapify
for(int i = arr.length - 1; i > 0; i--){ //O(N)
heapify(arr, i, arr.length);//O(logN)
}
}
public void heapSort2(int[] arr){
for(int i = 0;i < arr.length; i++){ //O(N)
heapInsert(arr,i);//O(logN)
}
}
public void bigHeapSort(int[] bigHeap){
int heapSize = bigHeap.length;
while(heapSize > 0){ //O(N)
swap(bigHeap,0,--heapSize);//O(1)
heapify(bigHeap,0,heapSize);//O(logN)
}
}
public void sort(int[] arr){
heapSort1(arr);//O(N)
bigHeapSort(arr);//O(N*logN)
}
private void heapify(int[] arr,int index,int heapSize) {
//左孩子下标
int left = index * 2 + 1;
//不越界时
while (left < heapSize) {
//获取较大孩子的下标
int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
//获取子树中最大值的下标
largest = arr[largest] > arr[index] ? largest : index;
//如果最大值就是自己,break
if (largest == index) {
break;
}
//自己和最大值交换
swap(arr, index, largest);
//下沉
index = largest;
//左孩子下标
left = index * 2 + 1;
}
}
private void heapInsert(int[] arr,int index){
while(arr[index] > arr[(index - 1) / 2]){
swap(arr,index,(index - 1) / 2);
index = (index - 1) / 2;
}
}
private void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
系统实现的堆PriorityQueue
几乎有序的数组
此处尽量有文字(否则可能会跳转到页面顶部)
题目:已知一个几乎有序的数组。几乎有序是指,如果把数组排好顺序的话,每个元素移动的距离一定不会超过k,并且k相对于数组长度来说是比较小的
请选择一个合适的排序策略,对这个数组进行排序
import java.util.PriorityQueue;
//在k小于数组长度时,时间复杂度O(N * logk)
//在k大于数组长度时,时间复杂度O(N * logN)
//所以在k小于数组长度时是非常好的排序策略
public class PriorityQueue_ {
public static void AlmostOrderly(int[] arr,int k){
PriorityQueue pq = new PriorityQueue<>();//小根堆
int index = 0;
//所有数依次入堆
for(int i = 0;i < arr.length;i++){//O(N)
pq.add(arr[i]);//O(1)
//前k + 1个数入堆后开始弹出
if(pq.size() > k + 1 ){//O(logk)
arr[index++] = pq.poll();
}
}
//弹出剩下的k个数 每次弹出O(logk)
//或者在数组长度不大于k的情况下,全部弹出 每次弹出O(logN)
while(!pq.isEmpty()){
arr[index++] = pq.poll();
}
}
}
比较器
用比较器把PriorityQueue改成大根堆
public static class MyComp implements Comparator前缀树{ @Override public int compare(Integer o1, Integer o2) { return o2 - o1; } } public static void main(String[] args) { PriorityQueue priorityQueue1 = new PriorityQueue<>(new MyComp()); //或者 PriorityQueue priorityQueue2 = new PriorityQueue<>(new Comparator () { @Override public int compare(Integer o1, Integer o2) { return o2 - o1; } }); }
import java.util.HashMap;
public class TrieTree {
public static class Node{
public int pass;//该节点被通过了多少次
public int end;//有多少字符串以此节点作为结尾
public HashMap next;//key -> 通往某个字符的路 , valve -> 此路指向的节点
public Node(){
pass = 0;
end = 0;
next = new HashMap<>();
}
}
public static class Trie{
private Node root;
public Trie(){
root = new Node();
}
public void insert(String s){
if(s == null){
return;
}
Node node = root;
node.pass++;
for(int i = 0; i < s.length(); i++){
if(!node.next.containsKey(s.charAt(i))){
node.next.put(s.charAt(i),new Node());
}
node = node.next.get(s.charAt(i));
node.pass++;
}
node.end++;
}
public int search(String s){
if(s == null){
return 0;
}
Node node = root;
for(int i = 0; i < s.length(); i++){
if(!node.next.containsKey(s.charAt(i))){
return 0;
}
node = node.next.get(s.charAt(i));
}
return node.end;
}
public void delete(String s){
if(search(s) == 0){
return;
}
Node node = root;
node.pass--;
for(int i = 0; i < s.length(); i++){
if(--node.next.get(s.charAt(i)).pass == 0){
node.next.remove(s.charAt(i));
return;
}
node = node.next.get(s.charAt(i));
}
node.end--;
}
public int prefixNumber(String pre){
if(pre == null){
return 0;
}
Node node = root;
for(int i = 0; i < pre.length(); i++){
if(!node.next.containsKey(pre.charAt(i))){
return 0;
}
node = node.next.get(pre.charAt(i));
}
return node.pass;
}
}
}



