算法总结（一）

归并分治

使用情况

  1. 左边结果+右边结果+跨越两边的结果是否等于最终结果
  2. 对于两边排序之后对于统计跨越两边的结果是否有帮助

注意与总结

  1. 主要思想跟归并排序一样 只不过是在merge的时候进行一些额外统计操作（统计跨越两边的结果）
  2. 如果只是单纯的比大小（比如 小和，逆序对）可以直接在merge的时候进行比较
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    //小和 直接在合并的时候进行比较统计
            while(a <=m && b<=r){
                if(nums[a]<nums[b]){
                    help[i++] = nums[a];
                    sum+= (nums[a]*(r-b+1));
                    a++;
                }else {
                    help[i++] = nums[b++];
                }
            }
  3. 如果不只是比大小 而是比较乘以二倍的结果，那么就需要在merge的时候 添加额外的统计操作
    1
    2
    3
    4
    5
    6
    7
    8
    //当左边的数大于右边的两倍时进行统计
            for(int ll=l,rr=m+1;ll<=m;ll++){
                while(rr<=r && (long)nums[ll]>((long)nums[rr]<<1)){
                    sum++;
                    rr++;
                }
                ans+=sum;
            }

快速排序

两种partition (普通+荷兰国旗)

  1. 普通partition 一次只能确定一个数的位置

核心思想：初始化索引i a xi
1.1 遍历数组，如果当前数小于等于x，则交换i和a数 i++ a++
1.2 如果大于x，则i++ a不动
1.3 如果遇到nums[a] == x,用xi记录他的位置
1.4 遍历结束后，交换xi和a-1的位置，让x放到对应的位置。
1.5 返回a-1（x应该在的位置）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//两个区号 小于等于   大于
    public static int partition1(int[] nums,int l,int r,int x){
        int i = l;
        int a = l;
        int xi = 0;
        while(i<=r){
            if(nums[i] <= x){
                swap(nums,a,i);
                if(nums[a] == x){
                    xi = a;
                }
                a++;
                i++;
            }else {
                i++;
            }
        }
        swap(nums,xi,a-1);
        return a-1;
    }
  1. 荷兰国旗partition 一次可以确定多个相同的数的位置

核心思路：初始化索引i a(小于区间) b（大于区间）
1.1 遍历数组，如果当前数小于x，则交换i和a数 i++ a++
1.2 如果大于x，则i不动 b—
1.3 如果等于x，则i++
1.4 遍历结束后，a-1（小于区间的末尾） b+1（大于区间的开头）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static int first,last;

//三个区间 小于  大于   等于
public static void partition2(int[] nums,int l,int r,int x){

    int a=l;
    int b=r;
    int i=l;
    while(i<=b){
        if(nums[i] < x){
            swap(nums,a++,i++);
        }else if(nums[i] > x){
            swap(nums,i,b--);
        }else {
            i++;
        }
    }
    first = a;
    last = b;
    }

扩展 快速选择

快速选择：给定一个数组，返回第k小的数

  1. 快速排序的思想，partition之后，如果在当前区间内的排名大于指定的排名，则递归quickselect(l,left-1,k)
  2. 快速排序的思想，partition之后，如果在当前区间内的排名小于指定的排名，则递归quickselect(right+1,r,k-rightNow) (rightNow指定的数在当前区间内的最靠右的排名)
  3. 快速排序的思想，partition之后，如果在当前区间内的排名等于指定的排名，则返回用于partition的数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int quick(int[] nums,int l,int r,int pos){
    if(l>=r){
        return nums[l];
    }
    int partitor = nums[l+ (int)(Math.random()*(r-l+1))];
    //荷兰国旗
    partition2(nums,l,r,partitor);
    int left = first;
    int right = last;
    int leftNow = left -l +1; //当前区间内partitor靠左的排名（可能存在多个partitor）
    int rightNow = right -l+1; //当前区间内partitor靠右的排名
    if(pos<leftNow){ //要找的位置在左边 再去左边找
        return quick(nums,l,left-1,pos);
    }else if(pos>rightNow){ //要找的位置在右边 再去右边找
        return quick(nums,right+1,r,pos-rightNow);
    }else { //要找的位置在中间 直接返回
        return nums[pos+l-1];
    }
}

堆排序

堆排序本身没什么好说的，就是利用堆这个数据结构进行排序。这里重点说一下heapify 跟 heapInsert

heapify

将节点下移到合适的位置，直接贴代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
   // i位置的数，变小了，又想维持大根堆结构
// 向下调整大根堆
// 当前堆的大小为size
public static void heapify(int[] arr, int i, int size) {
	int l = i * 2 + 1;
	while (l < size) {
		// 有左孩子，l
		// 右孩子，l+1
		// 评选，最强的孩子，是哪个下标的孩子
		int best = l + 1 < size && arr[l + 1] > arr[l] ? l + 1 : l;
		// 上面已经评选了最强的孩子，接下来，当前的数和最强的孩子之前，最强下标是谁
		best = arr[best] > arr[i] ? best : i;
		if (best == i) {
			break;
		}
		swap(arr, best, i);
		i = best;
		l = i * 2 + 1;
	}
}

也有递归的版本也很简单，这里不详细说了。

此外使用heapify可以自底向上的构建堆 时间复杂度为O(n)

1
2
3
4
      int n = arr.length;
for (int i = n/2 - 1; i >= 0; i--) {
	heapify(arr, i, n);
}

heapInsert

将节点上移到合适位置，直接贴代码

1
2
3
4
5
6
7
8
9
    // i位置的数，变大了，又想维持小根堆结构
// 向上调整小根堆
// 当前堆的大小为size
public static void heapInsert(int[] arr, int i) {
	while (arr[i] > arr[(i - 1) / 2]) {
		swap(arr, i, (i - 1) / 2);
		i = (i - 1) / 2
	}
}

此外使用heapInsert可以自上到下的构建堆 时间复杂度为O(n*logn) (不如上面的方法)

1
2
3
4
      int n = arr.length;
for (int i = 1; i < n; i++) {
	heapInsert(arr, i);
}

利用堆结构去解决一些其他问题

1. 合并k个有序链表

  1. 创建一个最小堆，将k个链表的头节点加入堆中
  2. 弹出最小的节点，并加入到结果链表中
  3. 弹出的节点的next节点加入堆中
  4. 重复2-3，直到堆为空
  5. 返回结果链表

复杂度 O(n*logk)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> heap = new PriorityQueue<>((a,b)->a.val-b.val);
    for (ListNode listNode : lists) {
        if(listNode!=null)
        {
            heap.add(listNode);
        }
    }
    if(heap.isEmpty()){
        return null;
    }
    ListNode h = heap.poll();
    ListNode pre =h;
    if(pre.next!=null){
        heap.add(pre.next);
    }
    while(!heap.isEmpty()){
        ListNode node = heap.poll();
        pre.next = node;
        if(node.next!=null){
            heap.add(node.next);
        }
        pre = node;
    }

    return h;
}

2. 线段最多重合问题

线段最多重合问题，就是给定很多线段，求线段最多重合的次数

  1. 将所有线段按开始的点进行排序
  2. 依次开始遍历线段
  3. 弹出堆中的最小点，如果最小点小于当前线段的开始点，则说明在当前线段开始时，这里面的线段已经结束不会重合。弹出堆中的最小点
  4. 循环3步直到堆里面的元素不小于当前线段的开始点。
  5. 将当前线段的结束点加入最小堆中
  6. 当前最小堆的size就是以这个线段开始为重合开始区间的重合的次数，用这个跟记录的最大次数进行比较，更新最大次数
  7. 循环2-6，直到所有线段都遍历结束
  8. 返回最大次数

时间复杂度 O(n*logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
   public static int compute() {
	// 堆的清空
	size = 0;

	// 线段一共有n条，line[0...n-1][2] : line[i][0] line[i][1], 左闭右闭
	// 所有线段，根据开始位置排序，结束位置无所谓
	// 比较器的用法
	// line [0...n) 排序 : 所有小数组，开始位置谁小谁在前
	Arrays.sort(line, 0, n, (a, b) -> a[0] - b[0]);
	int ans = 0;
	for (int i = 0; i < n; i++) {
		// i : line[i][0] line[i][1]
		while (size > 0 && heap[0] <= line[i][0]) {
			pop();
		}
		add(line[i][1]);
		ans = Math.max(ans, size);
	}
	return ans;
}

3.累加和减半最小操作次数

给你一个正整数数组 nums 。每一次操作中，你可以从 nums 中选择任意一个数并将它减小到恰好一半。（注意，在后续操作中你可以对减半过的数继续执行操作）
请你返回将 nums 数组和至少减少一半的最少操作数。

思路： 其实就是贪心算法，每次把最大的数减到一半，直到和减少到一半。其中找最大的数就可以用大根堆来实现。

  1. 创建一个大根堆，将数组中的数放入大根堆中。
  2. 取出最大的数，除以2 ，操作数++，并判断和是否减少到一半。如果和减少到一半，则返回当前操作数。
  3. 循环第二步。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
   public static int halveArray1(int[] nums) {
	// 大根堆
	PriorityQueue<Double> heap = new PriorityQueue<>((a, b) -> b.compareTo(a));
	double sum = 0;
	for (int num : nums) {
		heap.add((double) num);
		sum += num;
	}
	// sum，整体累加和，-> 要减少的目标！
	sum /= 2;
	int ans = 0;
	for (double minus = 0, cur; minus < sum; ans++, minus += cur) {
		cur = heap.poll() / 2;
		heap.add(cur);
	}
	return ans;
}

优化思路：可以自己实现大根堆，并且不用Double类型，用long类型将所有数乘以2的20次方，相当于小数部分可以保留20位，可以精确到小数点后20位。

基数排序

原理很简单 不细说 主要说说感悟

为什么要逆序遍历 Array：

  1. 排序的稳定性：
    在基数排序的实现中，逆序访问原数组 arr 的目的是为了保证排序的稳定性。稳定性是指排序算法在处理相等元素时能够保持它们在原数组中的相对顺序不变。
    在循环中，我们逆序遍历原数组 arr。这样做的好处是，当存在相等的元素时，先出现的元素会先放入对应的位置，而后出现的相等元素会放在它们之后的位置。这样可以保证相等元素的相对顺序不变，从而保证了排序的稳定性。
    如果我们采用顺序访问 arr 的方式，那么在处理相等元素时，后出现的相等元素可能会先放入对应的位置，从而打破了它们在原数组中的相对顺序，导致排序不稳定。
    因此，为了确保排序的稳定性，我们需要在逆序遍历原数组 arr 的情况下进行元素的放置操作。
  2. 自己的理解：
    2.1 基数排序，是基于数字的每一位（从低位到高位）进行排序，每一位的排序 基于 上一位（较低位）排好的基础上
    2.2 先将所有元素按照低位排序，再保持低位位序不变的情况下去排高位的位序（能让已经排好的低位的位序变化的原因只能受高位数值的影响）
    2.3 如果是顺序排序，那么低位顺序的改变不仅仅受到高位数值的影响，也受到错位的影响
    2.4 错位的影响：有数组：arr【 11 , 12 , 13 , 14 , 15】
    低位序已经排好，如果按照高位顺序遍历，会导致数组变成 【15 , 14 , 13 , 12 , 11】
    使得原先在 15 之前的 11 排在了 15 之后
    这种错位的影响是 顺序遍历 和 使用词频统计方法往Help中放元素(逆序) 相互作用决定的

排序算法总结

示例图片
示例图片