数据结构与算法笔记——By Bug

说明：本笔记为本人学习过程中随手写的笔记，为复习使用，笔记中可能存在遗漏或错误，具体请以官方文档和权威书籍为准！谢谢！

参考资料

书籍：
视频资料大厂必备数据结构与算法Java视频教程（上篇），java高级程序员必学的数据结构与算法哔哩哔哩bilibili 大厂必备数据结构与算法Java视频教程（下篇），java高级程序员必学的数据结构与算法哔哩哔哩bilibili
本笔记基于Java语言
题库：https://leetcode.cn/

基础知识需求

java语言基础
集合
泛型
多线程
数据库（选）
框架（选）

基础数据结构

二分查找

需求：在一个有序数组种查找值Target

算法描述

前提	一个含有n个元素的有序数组，满足升序排列，提供一个待查值t
1	设置两个指针，i=0， j=n-1
2	当i>j结束查找
3	获取中间元素索引m，小数向下取整
4	如果target<Am，j=m-1，回到步骤2
5	如果target>Am，i=m+1，回到步骤2
6	如果target=Am，找到结果，结束查找

算法实现

基础版


xxxxxxxxxx
public int search(int[] nums, int target) {
        int i= 0;
        int j = nums.length-1;
       
        while(i<=j){
            int m =(i+j)/2;
            if(nums[m]<target)i=m+1;            
            else if(target<nums[m])j=m-1;
            else 
                return m;   
            }
            return -1;
    }

改动版


xxxxxxxxxx
 public static void main(String[] args) {
        int[] a = {0,1,2,3,4,5,6,7,8,9};
        Scanner in = new Scanner(System.in);
        int innum = in.nextInt();
        int i=0;
        int j = a.length;//改动1  a.length-1 --》a.length

        while (i<j){ //改动2 i<=j --》i<j
            int m = (i+j)>>>1;
            if (a[m]>innum){
                j=m;  //改动3 j=m-1 --》j=m
            }
            else if(a[m]<innum){
                i=m+1;
            }
            else {
                System.out.println("找到了"+a[m]);
            break;
            }
        }
 }

JAVA二分查找方法binarySearch


xxxxxxxxxx
 public static void main(String[] args) {

        int[] a = {0,1,2,3,4,5,6,7,8,9};
        int c =Arrays.binarySearch(a,3);//找到返回索引
        System.out.println(c);
        int d =Arrays.binarySearch(a,100);//未找到返回 负（插入点+1） 
        System.out.println(d);
    }

二分查找处理重复数据

需求：返回重复数据的最左侧一个的下标


xxxxxxxxxx
public static void main(String[] args) {

        int[] a = {0,1,2,3,3,3,4,5,6,7,8,9};
        Scanner in = new Scanner(System.in);
        int innum = in.nextInt();
        int i=0;
        int j = a.length-1;
        int w = 0;//候选位置下标
        while (i<=j){
            int m = (i+j)>>>1;
            if (a[m]>innum){
                j=m-1;
            }
            else if(a[m]<innum){
                i=m+1;
            }
            else {
                w=m;
                j=m-1;//修改j的值为m-1
            }
        }
        System.out.println(w);
    }

需求：返回重复数据的最右侧一个的下标


xxxxxxxxxx
public static void main(String[] args) {

        int[] a = {0,1,2,3,3,3,4,5,6,7,8,9};
        Scanner in = new Scanner(System.in);
        int innum = in.nextInt();
        int i=0;
        int j = a.length-1;
        int w = 0;//候选位置下标
        while (i<=j){
            int m = (i+j)>>>1;
            if (a[m]>innum){
                j=m-1;
            }
            else if(a[m]<innum){
                i=m+1;
            }
            else {
                w=m;
                i=m+1;//修改i的值为m+1
            }
        }
        System.out.println(w);
    }

衡量算法的好坏

时间复杂度

常见大 $O$ 表示法

按时间复杂度从低到高

黑色横线 $O(1)$，常量时间，意味着算法时间并不随数据规模而变化
绿色 $O(log(n))$，对数时间
蓝色 $O(n)$，线性时间，算法时间与数据规模成正比
橙色 $O(n*log(n))$，拟线性时间
红色 $O(n^2)$ 平方时间
黑色朝上 $O(2^n)$ 指数时间
没画出来的 $O(n!)$

空间复杂度

算法占用的内存情况等。

二分查找的性能

时间复杂度

最坏情况：O(logn)
最好情况：O(1)

空间复杂度

需要常数个指针i,j,m，因此额外占用空间是O(1)

数组

概述

数组就是由一组元素组成的数据结构。每个元素至少一个索引或键来标识。

数组中的元素是连续存储的。

动态数组

数组默认是不能对数组进行增删操作的，可以使用动态数组进行增删改查数据

实现动态数组


xxxxxxxxxx
package com.java.shujv1;

import java.util.Arrays;

public class 动态数组 {
    private int size = 0;
    private int capacity = 10;
    private int[] a = new int[capacity];

    public int[] getA() {
        return a;
    }
    public void addlast(int b){
        addindex(b,size);
    }

    public void addindex (int b,int index){
        if(size >=capacity){
            capacity+=capacity>>>1;
            int[] newarr = new int[capacity];
            System.arraycopy(a,0,newarr,0,size);
            a = newarr;

        }
        if (index>=0&&index<size){
            System.arraycopy(a,index,a,index+1,size-index);
        }
        a[index] = b;
        size++;
    }
    public void remove(int index){
        System.arraycopy(a,index+1,a,index,size-index);
    }
}

二维数组


xxxxxxxxxx
int[][] a = {
                {1,2,3},
                {4,5,6},
                {7,8,9}
        };

链表

链表是数据元素的线性集合，其中每个元素都指向下一个元素，元素存储上并不连续。

链表可分为：

单向链表：每个元素都只指向下一个元素
双向链表：每个元素都指向上一个元素和下一个元素。
循环链表：链表的尾节点指向头节点

链表的一个特殊节点：哨兵节点，也称哑元节点，它不存储数据，通常作为头尾使用。