数组概述

数组的定义：在连续的内存空间中，储存一组相同类型的元素

数组的访问：通过索引访问元素
数组的搜索：找到这个元素对应的索引

数组的四种操作

任意数据结构基本都要讨论这四种操作，对比两个数据结构也是从这四种操作入手

访问 Access 时间复杂度 O(1)
通过计算可以得到地址位置，从而进行访问
搜索 Search 时间复杂度 O(N)
需要对数组进行遍历
插入 Insert 时间复杂度 O(N)
- 需要将后面的元素往后移动
- 如果内存不够，需要开辟一块新空间，将数组移进去
删除 Delete 时间复杂度 O(N)
需要将后面元素往前移

数组特点

适合读
不适合频繁做增删操作
场景：读多写少

数组实际的常用操作（Java）

9_Java集合

创建数组

      //Four solutions to create an array in Java
      //Take [1,2,3] as example
      //Solution 1
      int[] a = {1, 2, 3};
      System.out.println("a:" + Arrays.toString(a));
      //Solution 2
      int[] b = new int[]{1, 2, 3};
      System.out.println("b:" + Arrays.toString(b));
      //Solution 3
      int[] c = new int[3];
      for (int i = 0; i < a.length; i++) {
          c[i] = i + 1;
      }
      System.out.println("c:" + Arrays.toString(c));
      //Solution 4
      ArrayList<Integer> arr = new ArrayList<>();
      for (int i = 0; i < 3; i++) {
          arr.add(i + 1);
      }
      System.out.println("arr:" + arr.toString());

添加元素

      //Add element 空间足够，尾部添加
      //Time Complexity:O(1)
      arr.add(99);
      //[1,2,3,99]
      System.out.println("arr:" + arr.toString());
      //Insert element 中间插入
      //Time Complexity:O(N)
      arr.add(3, 88);
      //[1,2,3,88,99]
      System.out.println("arr:" + arr.toString());

访问元素

      //Access element
      //Time Complexity:O(1)
      int c1 = c[0];
      int arr1 = arr.get(0);
      //1
      System.out.println("c1:" + c1);
      System.out.println("arr1:" + arr1);

修改元素

      //Update element 先访问后修改
      //Time Complexity:O(1)
      c[0] = 11;
      arr.set(0, 11);
      //1->11
      System.out.println("c1:" + c[0]);
      System.out.println("arr1:" + arr.get(0));

删除元素

      //Remove element
      //Time Complexity:O(N)
      arr.remove(0);
      System.out.println("arr1:" + arr.get(1));

数组的长度

      //The length of an array
      //Time Complexity:O(1)
      int cSize = c.length;
      int arrSize = arr.size();
      System.out.println("c length:" + cSize);
      System.out.println("arr length:" + arrSize);

遍历元素

      //Iterate an array
      //Time Complexity:O(N)
      //Iterate c
      for (int i = 0; i < c.length; i++) {
          int current = c[i];
          System.out.println("c at index " + i + ":" + current);
      }
      //Iterate arr
      for (int i = 0; i < arr.size(); i++) {
          int current = arr.get(i);
          System.out.println("arr at index " + i + ":" + current);
      }

查找元素

      //Find an element
      //Time Complexity:O(N)
      //Find an element in c 
      for (int i = 0; i < c.length; i++) {
          if (c[i] == 99) {
              System.out.println("We found 99 in c!");
          }
      }
      //Find an element in arr 
      boolean is99 = arr.contains(99);
      System.out.println("Are we found 99 in arr?" + is99);

数组的排序

      //Sort an array by built-in Lib 
      c = new int[]{2, 3, 1};
      arr = new ArrayList<>();
      arr.add(2);
      arr.add(3);
      arr.add(1);
      //[2,3,1]
      System.out.println("c:" + Arrays.toString(c));
      System.out.println("arr:" + arr.toString());
      //From small to big
      //Time complexity:O(NLogN)
      Arrays.sort(c);
      Collections.sort(arr);
      //[1,2,3]
      System.out.println("c:" + Arrays.toString(c));
      System.out.println("arr:" + arr);
      //From big to small
      //Time complexity:O(NLogN)
      //For c, you can read an array in reverse
      //Arrays.sort(T[], Collections.reverseOrder());
      //For arr 
      Collections.sort(arr, Collections.reverseOrder());
      //[3,2,1]
      System.out.println("arr:" + arr);

LeetCode练习

#485

#283

#27

参考：https://www.bilibili.com/read/cv8568185?spm_id_from=333.788.b_636f6d6d656e74.6

计算机基础

数据结构一：数组 Array

数组概述

数组的四种操作

数组特点

数组实际的常用操作（Java）

LeetCode练习