二分、复杂度、动态数组、哈希表

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

1.二分法 不一定一定有序比如找局部最小值就可以不有序

有序数组中找到num

用对数器生成随机数组来校验find()方法是否正确

public class Code01_BSExist {
    //有序数组中找到num
    //arr保证有序
    public static boolean find(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        int L = 0;
        int R = arr.length - 1;
        //arr[0,N-1]  arr[L,R]
        while (L <= R) {
            int mid = (L + R) / 2;
            if (arr[mid] == num){
                return true;
            }else if(arr[mid]<num){//如果arr[mid]<num则arr[mid]左边的数都不符合都排除掉L = mid + 1
                L = mid + 1;
            }else {
                R = mid - 1; //如果arr[mid]>num则arr[mid]右边的数都不符合都排除掉R = mid - 1
            }
        }
        return false;
    }
    // for test 暴力测试
    public static boolean test(int[] sortedArr, int num) {
        for (int cur : sortedArr) { //增强for循环遍历
            if (cur == num) {
                return true;  //找到num返回true
            }
        }
        return false; //找不到返回false
    }

    // for test
    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++) {//给数组每一个位置生成随机数
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 10;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
            Arrays.sort(arr);//Arrays.sort默认从小到大排序
            int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());//生成一个随机num
            if (test(arr, value) != find(arr, value)) {
                System.out.println("出错了");
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }
}

image-20230112101441213

有序数组中找到>=num最左的位置

package class03;

import java.util.Arrays;

public class Code02_BSNearLeft {
    //有序数组中找到>=num最左的位置  最左不小于num的索引位置
    public static int mostLeftNoLessNumIndex(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int L = 0;
        int R = arr.length - 1;
        int ans = -1;
        //1.有序数组中找到>=num最左的位置
        /*while (L <= R) {
            int mid = (L + R) / 2;
            if (arr[mid] >= num){
                ans = mid;//不断更新ans值也就是索引位置如果arr[mid] = num成立也就是找到了num值最后一次更新的位置就是要找的位置
                R = mid - 1;
            }else {
                L = mid + 1;
            }
        }*/
        
        //2.有序数组中找到<=num最右的位置
        while (L <= R) {
            int mid = (L + R) / 2;
            if (arr[mid] > num) {
//不断更新ans值也就是索引位置如果arr[mid] == num成立也就是找到了num、mid值最后一次更新的位置就是要找的位置mid,
//如果在这个过程中始终没有找到或者arr[mid] > num就不更新ans值比如如果数组{1,2,3,4}我们找100
// 一直都找不到arr[mid]>100的值ans值就一直不更新,但是我们这里是要找100在最右侧出现所以当arr[mid] <= 100时就不断更新ans值不断去找寻这个arr[mid]==100的位置,所以条件一不更新条件二不断的更新ans值直到找到合适的mid值这个mid就是我们要找的位置
//如果这个数组中的全部数都大于num就一直执行arr[mid] > num这个条件ans一直不更新最后ans的返回值就是-1
                R = mid - 1;
            } else {
                ans = mid;
                L = mid + 1;
            }
        }
        return ans;
    }
//==============================================================================================
    // 1.for test 有序数组中找到>=num最左的位置
/*    public static int test(int[] arr, int value) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] >= value) {
                return i;
            }
        }
        return -1;
    }*/
    
    //2.有序数组中找到<=num最右的位置
    public static int test(int[] arr, int value) {
        for (int i = arr.length-1; i > 0; i--) {
            if (arr[i] == value) {
                return i;
            }
        }
        return -1;
    }
//===================================================================================================
    // for test
    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++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }
    
public static int test(int[] arr, int value) {
        //i >= 0这里i一定要把等于0写上因为如果左右出现的数在0就需要返回0索引了
        for (int i = arr.length-1; i >= 0; i--) {
            if (arr[i] <= value) {
                return i;
            }
        }
        return -1;
    }


    public static void main(String[] args) {
        int testTime = 50;
        int maxSize = 10;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
//            int[] arr = {1, 2, 3, 5, 6, 6, 6, 6, 7, 8, 9};
            Arrays.sort(arr);
            int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
//            int value = 6;
            if (test(arr, value) != mostLeftNoLessNumIndex(arr, value)) {
                printArray(arr);
                System.out.println(value);
                System.out.println(test(arr, value));
                System.out.println(mostLeftNoLessNumIndex(arr, value));
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");
    }
}

image-20230112114924609

局部最小值问题 需要数与数之间相邻不等

package class03;
public class Code03_BSAwesome {
    public static int oneMinIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int N = arr.length;
        if (N == 1) {
            return 0;
        }
        if (arr[0] < arr[1]) {
            return 0;
        }
        if (arr[N - 1] < arr[N - 2]) {
            return N - 1;
        }
        int L = 0;
        int R = N - 1;//L...R肯定有局部最小
        while (L < R - 1) {
            int mid = (L + R) / 2;
            if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                return mid;
            } else {
                //三种情况 1.左>mid mid>右、2.左<mid mid>右、3.左<mid mid<右
                //2.3情况
                if (arr[mid] > arr[mid - 1]) {
                    R = mid - 1; //局部最小值肯定在左边右边可能有可能没有但是只要一个局部最小所以把右边的值都砍掉
                    // 因为arr[mid]大于arr[mid-1]的值
                }
                //1.情况
                else {//arr[mid] >arr[mid+1]  左边的数都砍掉局部最小肯定在右边左边可能有可能没有
                    L = mid + 1;
                }
            }
        }
        return arr[L] < arr[R] ? L : R;
    }

    //生成随机数组且相邻数不相等
    public static int[] randomArray(int maxLen, int maxValue) {
        int len = (int) (Math.random() * maxLen);
        int[] arr = new int[len];
        if (len > 0) {
            arr[0] = (int) (Math.random() * maxValue);
            for (int i = 1; i < len; i++) {
                //先执行一次然后判断如果arr[i] == arr[i - 1]就重做如果不相等就继续执行下一次for循环重复上述过程
                do {
                    arr[i] = (int) (Math.random() * maxValue);
                } while (arr[i] == arr[i - 1]);
            }
        }
        return arr;
    }

    public static boolean check(int[] arr, int minIndex) {
        if (arr.length == 0) {
            return minIndex == -1;
        }
        int left = minIndex - 1;
        int right = minIndex + 1;
        //先判断是否越界如果没越界就比较一下
        boolean leftBigger = left >= 0 ? arr[left] > arr[minIndex] : true;
        boolean rightBigger = right < arr.length ? arr[right] > arr[minIndex] : true;
        return rightBigger && leftBigger;
    }

    //打印数组
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int maxLen = 100;
        int maxValue = 20;
        int testTimes = 1000000;
        System.out.println("测试开始");
        for (int i = 0; i < testTimes; i++) {
            int[] arr = randomArray(maxLen, maxValue);
            int ans = oneMinIndex(arr);
            if (!check(arr, ans)) {
                printArray(arr);
                System.out.println(ans);
                break;
            }
        }
        System.out.println("测试结束");
    }
}

image-20230112174838912

2.时间复杂度

等差数列中时间复杂度为ON

二分中时间复杂度为
O ( log ⁡ 2 N ) O (\log_2{N}) O(log2​N)
常数操作时间复杂度O1

最差的情况来估计时间复杂度

3.动态数组

在java中arraylist是动态数组时间复杂度是O1每往数组中新加数如果下标越界就会进行数组扩容数组长度扩容到原本的2倍扩容的过程是一个等差数列扩容前的数组元素原封不动复制到扩容后的数组然后新加的元素插入到新数组后面

o10n

4.哈希表与有序表

哈希表<K,V>

  • 哈希表的增删改查时间复杂度都为O1但是这个常数时间是比较大的

  • 哈希表中按值传递不看地址是否不同

public static class Node {
        public int value;

        public Node(int v) {
            value = v;
        }
    }

    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<>();
        map.put("name", "我是佩萁");
        System.out.println(map.containsKey("name"));//true
        System.out.println(map.get("name"));//我是佩萁
        map.put("name", "小熊");
        System.out.println(map.get("name"));//小熊


        HashMap<Integer, String> map2 = new HashMap<>();
        map2.put(123456, "我是1234567");
        Integer a = 123456;
        Integer b = 123456;
        //==比较的是内存地址  如果要比较后面的内容应该写equals方法
        System.out.println(a == b);//false
        //哈希表只看后面的内容不看内存地址是否不一样
        System.out.println(map2.containsKey(a));//true
        System.out.println(map2.containsKey(b));//true

        //如果是自己写的类型的话就不是单看值是否相等了而是看地址是否一样
        Node node1 = new Node(1);
        Node node2 = new Node(1);
        HashMap<Node,String> map3 = new HashMap<>();
        map3.put(node1,"我是node1");
        System.out.println(map3.containsKey(node1));//true
        System.out.println(map3.containsKey(node2));//false
    }

有序表

  • 有序表的每步时间复杂度都为ON

  • 有序表传入的key值必须可以比较如果不是基础类型而是自己定义的类型需要说明怎么比较否则会报错

        TreeMap<Integer,String> treeMap1 = new TreeMap<>();
        treeMap1.put(3,"我是3");
        treeMap1.put(0,"我是0");
        treeMap1.put(6,"我是6");
        treeMap1.put(4,"我是4");
        treeMap1.put(5,"我是5");
        treeMap1.put(8,"我是8");
        System.out.println(treeMap1.containsKey(4));//true
        System.out.println(treeMap1.get(4));//我是4
        System.out.println(treeMap1.firstKey());//0 找到最小的key值
        System.out.println(treeMap1.lastKey());//8 找到最大的key值
        System.out.println(treeMap1.floorKey(5));//5  <=5 离5最近的key
        System.out.println(treeMap1.ceilingKey(6));//6  >=6 离6最近的key
阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
返回列表

上一篇：【day1】谷粒商城-人人开源前后端联调准备工作

下一篇：如何设计一个消息队列

“二分、复杂度、动态数组、哈希表” 的相关文章

【Linux】-- 进程概念1年前 (2023-02-02)
Web前端：2023年使用的9个最佳JavaScript框架1年前 (2023-02-02)
React脚手架应用（二）1年前 (2023-02-02)
LeetCode刷题第八九十周1年前 (2023-02-02)
一文读懂 HTTP/1 HTTP/2 HTTP/31年前 (2023-02-02)
【新知实验室 - TRTC 实践】音视频互动 Demo、即时通信 IM 服务搭建1年前 (2023-02-02)
学习笔记——CentOS中的帮助命令；常用快捷键；文件目录类命令1年前 (2023-02-02)
学习笔记——安卓的下载路径；创建一个空的安卓project；Android中的日志工具划分1年前 (2023-02-02)
操作系统的概念、功能和目标1年前 (2023-02-02)
vue传数组参数给java后端1年前 (2023-02-02)

阿里云国际版