[数据结构与算法]【算法集训】算法之反转链表、快速排序和二分查找

大家好！我是未来村村长，就是那个“请你跟我这样做，我就跟你这样做！”的村长👨?🌾！

||Algorithm Day||

? 未来村村长正推出一系列【Algorithm Day】文章，该系列文章重在提高本人的算法能力，希望能在刷题过程中总结一般方法，提高个人的逻辑思维能力和解题能力。该系列文章以天数为轴，从一个个算法中逐步强化算法相关知识点。

? ”算法之路，任重而道远。“🌱[day 1]🌾

? 此篇文章包含三个算法：反转链表、快速排序、二分查找

? [声明：以下题目的内容或部分解法来自牛客网或Leetcode，为个人学习总结和记录，也方便大家学习和查阅]

一、反转单链表

1、题目描述

（1）描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： n∈[0,1000]

要求：空间复杂度 O(1)，时间复杂度 O(n)。

（2）示例

例子：

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

2、思路分析

（1）实现一思路

? 使用栈，将链表节点一个个入栈，当全部入栈后再一个个出栈

Stack<ListNode> stack= new Stack<>();

（2）实现二思路

? 将原链表的结点从头开始摘掉，每次摘得的节点都让它成为新的链表头结点

3、Java实现

（1）方法一：使用栈

import java.util.Stack;
public class Solution {
    public ListNode ReverseList(ListNode head) {
    	//1、建立一个栈
        Stack<ListNode> stack = new Stack<>();
        
        //2、取出链表节点到栈中
        while(Head != null){
            stack.push(head);
            head = head.next;
        }
        
        //错误判定
        if(stack.isEmpty()) return null;
        
        //3、从栈中取出一个节点【新头节点】
        ListNode newHead = stack.pop();
        
        //4、取出栈所有节点，每次取出作为上一次取出的后继节点
        ListNode temp = newHead;
        while(!stack.isEmpty()){
            temp.next = stack.pop();
            temp = temp.next;
        }
        
        //5、将最后取出的节点【原头节点】的后继置为null
        temp.next = null;
        
        //6、返回新头节点
        return newHead;
    }
}

（2）方法二：逐个摘出为新头

? 相当于是两个链表，一个从头取出，然后从头插入另一个链表

public class Solution {
    public ListNode ReverseList(ListNode head) {
        //1.创建一个新链表【头结点】
        ListNode newHead = null;
        //2.从原来链表的头部不断取出节点，一次取一个【头节点】
        while( head != null){
            //2.1拿到头节点后一个节点
            ListNode temp = head.next;
            //2.2取出头节点
            head.next = newHead;
            //2.3更新newHead为拿到的头节点
            newHead = head;
            //2.4更新head为原头结点的下一个节点
            head = temp;
        }
       	//3.返回新头节点
        return newHead;
    }
}

4、相关知识补充【常用数据结构】

（1）栈Stack

? 创建

Stack<Object> stack= new Stack<>();

（2）队列Queue

? 创建

LinkedList<Object> list = new LinkedList<>();

（3）堆

? 堆其实就是一种特殊的队列——优先队列。

? 这篇说得好：https://blog.csdn.net/u010285974/article/details/107712892

? 二叉堆是基于完全二叉树实现，其有两种类型：

• 大顶堆：每个节点的关键字都大于其孩子节点的关键字，根节点是堆中最大节点【因为双亲节点总是大于孩子节点，所以从根节点出发，无论走那条路，得到的都是一个递减序列，可证明根节点为堆中最大节点】

• 小顶堆：每个节点的关键字都小于其孩子节点的关键字，根节点是堆中最小节点

  通过数组建造大顶堆，就是通过sink算法，将数组每个元素进行下沉操作

    private static void sink(int[] arr,int index,int length){
        //index：代表进行下沉操纵的节点
        //左子节点下标
        int leftChild = 2*index + 1;
        //右子节点下标
        int rightChild = 2*index + 2;
        //要调整的节点下标
        int present = index;
		
        //向左边下沉
        if(leftChild<length && arr[leftChild]>arr[present]){
            present = leftChild;
        }
		
        //向右边下沉
        if(rightChild<length && arr[rightChild]>arr[present]){
            present = rightChild;
        }
		
        //如果下标不相等，说明下标已经下沉
        if(present!=index){
            //则交换值达到值的下沉
            int temp = arr[index];
            arr[index] = arr[present];
            arr[present] = temp;
			//继续下沉
            sink(arr,present,length);
        }

? 建造堆。

  private static void buildHeap(int[] arr,int length){
       //从length/2的位置开始向前遍历，因为length/2后的节点皆为孩子节点
        for (int i = length/2; i>=0; i--) {
            //对length/2之前的双亲节点逐个进行下沉操作
            sink(arr,i,length);
        }
    }

二、排序

1、题目描述

（1）描述

? 给定一个长度为 n 的数组，请你编写一个函数，返回该数组按升序排序后的结果。

? 要求：时间复杂度 O(n²)，空间复杂度 O(n)

? 进阶：时间复杂度 O(nlogn)，空间复杂度 O(n)

（2）示例

?

2、思路分析

（1）实现一思路

? 使用Arrays.sort

Arrays.sort(arr);

（2）实现二思路

? 快速排序：快速排序采用的是分治的思想，不断递归【设定一个基准位，将该数组分成两份】，实现数组的排序。

3、Java实现

（1）实现一：Arrays

import java.util.*;

public class Solution {
    public int[] MySort (int[] arr) {
        Arrays.sort(arr);
        return arr;
    }
}

（二）实现二：快排

import java.util.*;


public class Solution {
    public int[] MySort (int[] arr) {
        QSort(arr,0,arr.length-1);
        return arr;
    }
    
    public void QSort (int[] arr,int low,int high) {
    	//一、属性定义
        int i,j;//1、左右扫描指针
        if(low>high) return;//2、当low与high大小相等时结束递归
        i = low;//3、i从左开始扫描
        j = high;//4、j从右开始扫描
        int temp = arr[low];//5、基准位

        //二、排序实现【升序】
        while (i<j){
            //1、i，j分别从两边开始扫描
            while (arr[j]>=temp && j>i) j--;
            while (arr[i]<=temp && j>i) i++;
            //2、j停下来的数小于基准位，i则大于基准位
            //3、将i和j的数字进行交换
            if(j>i){
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        //4、归位：ij相遇的位置就是基准位的位置
        arr[low] = arr[i];
        arr[i] = temp;

        //三、递归执行
        QSort(arr,low,j-1);
        QSort(arr,j+1,high);
    }
}

4、相关知识补充【Arrays的使用】

（1）Arrays的常用方法

三、二分查找

1、题目描述

（1）描述

? 请实现有重复数字的升序数组的二分查找

? 给定一个 元素有序的（升序）长度为n的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的第一个出现的target，如果目标值存在返回下标，否则返回 -1

? 进阶：时间复杂度O(logn) ，空间复杂度O(n)

（2）示例

2、思路分析

? ① 使用while循环来实现二分查找，将目标数值与数组中心数进行比较。

? ② 如果目标数大于中心数，则又从右边取中心数进行比较；如果目标数大于中心数，则又从左边取中心数进行比较，直到数组中心数等于目标数。

? ③ 此时可能还有首次出现的数在中心数的左边，这时向左遍历看是否有相同的值。

3、Java实现

import java.util.*;
public class Solution {
    public int search (int[] nums, int target) {
        //1.取到数组的长度
        int l = nums.length;
        //错误判断:超出数组范围，则返回-1
        if(l==0 || nums[0]>target || nums[l-1]<target) return -1;
        //2.通过二分法进行查找
        int i = 0,j = l-1,mid = 0;
        while(i<=j){
            //2.1 取到mid
            mid = (i+j)/2;
            //2.2 更改mid
        	if(target>nums[mid]) i = mid + 1;
        	if(target<nums[mid]) j = mid - 1;
            //2.3 直到找到对应的值
            if(target==nums[mid]){
            	//向左遍历
                while(mid>0 && nums[mid-1]==target) mid--;
                return mid;
            }   
        }
        return -1;   
    }
}

4、相关知识补充

? 由二分查找可以拓展到二叉查找树，由二叉查找树可以拓展到B树，然后到红黑树，之后到B+树。

创作挑战赛

新人创作奖励来咯，坚持创作打卡瓜分现金大奖