数据结构与算法 - 数组

待我称王封你为后i 2024-03-26 20:19 25阅读 0赞

#### 数据结构与算法 - 数组 ####

#### 文章目录 ####

*   *   *  数据结构与算法 - 数组
         *   *  1 介绍
             *  2 一维数组的初始化
             *  3 数组的优缺点
             *   *  【优点：数组访问元素高效】
                 *  【缺点：数组在初始化后长度不可变】
                 *  【缺点：数组中插入或删除元素效率低下】
                 *  【总结】
             *  4 数组的常用操作
             *   *  【1】数组的遍历
                 *  【2】数组查找
             *  5 Arrays工具类
             *   *  ① Arrays.fill()
                 *  ② Arrays.sort()
             *  6 LeetCode - 数组

![在这里插入图片描述][5cf7428427c34ed5abb50fd19f1ca4fb.png]

> 【原作者】[@Krahets][Krahets]
> 
> 【Hello 算法】[https://www.hello-algo.com/][https_www.hello-algo.com]

##### 1 介绍 #####

数组Array 是一种将`相同类型元素` 存储在 `连续内存空间` 的数据结构，将元素在数组中的位置称为元素的 `索引Index`。

![在这里插入图片描述][8799809ae0514e02b64444035432a969.png_pic_center]

##### 2 一维数组的初始化 #####

Java中常见的数组初始化方法。

package initialization;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: CreateArray
     * @Author: Ding Jiaxiong
     * @Data:2023/3/10 13:12
     */
    public class CreateArray {
        
        public static void main(String[] args) {
        
    
            // 动态初始化
            int[] arr1 = new int[5]; // 【推荐】
            int arr2[] = new int[5];
    
            // 静态初始化
            int[] arr3 = new int[]{
        1, 2, 3, 4, 5};
            int[] arr4 = {
        1, 2, 3, 4, 5};
            //【当然不管是动态初始化还是静态初始化都可以分步完成, 即先声明, 再初始化赋值】
    
        }
    }

##### 3 数组的优缺点 #####

###### 【优点：数组访问元素高效】 ######

这是因为在数组中，计算元素的内存地址非常容易，给定数组首个元素的地址和需计算元素的索引，利用下面的公式可以直接计算得到该元素的内存地址，从而直接访问该元素。

![在这里插入图片描述][2b70bd5a07c14c9e84de17df4f1bdd47.png_pic_center]

根据这个公式，数组中首个元素的地址偏移量是0，所以索引为0 。

我们可以在 O ( 1 ) O(1) O(1) 的时间内随机获取一个数组中的元素。

###### 【缺点：数组在初始化后长度不可变】 ######

由于系统无法保证数组之后的内存空间可用，所以数组长度是没有办法进行扩展的，如果真的希望扩容数组，则需要新建一个数组，然后原数组中的元素拷贝到新数组，才能完成扩容。

###### 【缺点：数组中插入或删除元素效率低下】 ######

数组中插入一个新元素。由于数组元素在内存中是紧挨着的，所以它们之间没有空间来再存放新的数据，所以要想实现插入，就需要将索引之后的所有元素都向后移。

![在这里插入图片描述][0cf3c151a675432d858679859284af67.png_pic_center]

删除元素也类似，指定索引处的元素被删除后，需要把指定索引之后的元素都向前移动一位。

![在这里插入图片描述][61733a98d2b34e10bdbcc9ed20304a95.png_pic_center]

###### 【总结】 ######

*  数组的插入和删除平均时间复杂度 O ( N ) O(N) O(N)
 *  由于数组长度不可变，因此插入元素后，超出数组长度的元素会丢失。
 *  正因为数组长度不可变，所以我们在初始化时，需要慎重考虑，一般就会初始化一个比较长的数组，这样做虽然可能避免了丢失元素，但是会造成内存空间的浪费。

##### 4 数组的常用操作 #####

###### 【1】数组的遍历 ######

两种常见的遍历方法。

package arraytraversal;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: ArrayTraversal
     * @Author: Ding Jiaxiong
     * @Data:2023/3/10 13:47
     */
    
    public class ArrayTraversal {
        
    
        public static void main(String[] args) {
        
    
            // 初始化两个数组
            int[] arr1 = new int[5];
            int[] arr2 = new int[]{
        1, 2, 3, 4, 5};
    
            // 遍历方式1: 根据索引遍历
            System.out.print("arr1: ");
            for (int i = 0; i < arr1.length; i++) {
        
                System.out.print(arr1[i] + " ");
            }
    
            // 遍历方式2: foreach
            System.out.print("\narr2: ");
            for (int element : arr2) {
        
                System.out.print(element + " ");
            }
        }
    
    }

![在这里插入图片描述][b45c4be03b6e4d858a5ce92c5a05dbb1.png_pic_center]

###### 【2】数组查找 ######

通过遍历数组，查找数组内的指定元素，并输出对应索引。

package arraysearch;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: ArraySearch
     * @Author: Ding Jiaxiong
     * @Data:2023/3/10 13:52
     */
    
    public class ArraySearch {
        
    
        public static int find(int[] nums, int target) {
        
    
            for (int i = 0; i < nums.length; i++) {
        
                if (nums[i] == target) {
        
                    return i;
                }
            }
            return -1; // 没找到返回-1
        }
    
        public static void main(String[] args) {
        
    
            int[] test = new int[]{
        1, 2, 3, 4, 5};
            System.out.println(find(test, 3));
        }
    
    }

![在这里插入图片描述][23800feb88e647e2b80bc088233ca22b.png_pic_center]

##### 5 Arrays工具类 #####

###### ① Arrays.fill() ######

此方法用于对指定数组进行赋值操作。

package arraysmethods;
    
    import java.util.Arrays;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: FillTest
     * @Author: Ding Jiaxiong
     * @Data:2023/3/9 16:48
     */
    
    public class FillTest {
        
    
        public static void main(String[] args) {
        
    
            int[] arr1 = new int[5];
            int[] arr2 = new int[5];
            // 两个参数
            Arrays.fill(arr1, 666);
            System.out.print("arr1: ");
            for (int e : arr1) {
        
                System.out.print(e + " ");
            }
            System.out.println("\n==========");
            // 四个参数
            Arrays.fill(arr2, 1, 3, 55);
            System.out.print("arr2: ");
            for (int e : arr2) {
        
                System.out.print(e + " ");
            }
        }
    
    }

![在这里插入图片描述][1bad5a137d804d4b9bae6eacc6ae04e0.png_pic_center]

###### ② Arrays.sort() ######

package arraysmethods;
    
    import java.util.Arrays;
    import java.util.Collections;
    import java.util.Comparator;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: SortTest
     * @Author: Ding Jiaxiong
     * @Data:2023/3/10 14:00
     */
    
    public class SortTest {
        
    
        public static void sort01(int[] nums) {
        
            // 默认升序
            Arrays.sort(nums);
        }
    
        public static void sort02(int[] nums, int fromIndex, int toIndex) {
        
            // 【升序】指定排序元素范围，fromIndex(包含) ~ toIndex(不包含)
            Arrays.sort(nums, fromIndex, toIndex);
        }
    
    
        public static void sort03(Integer[] nums) {
        
            // 降序排序实现1: 利用自带方法【注意这里要用包装类】
            Arrays.sort(nums, Collections.reverseOrder());
        }
    
        public static void sort04(Integer[] nums) {
        
            // 降序排序实现2: 重载比较器
            Arrays.sort(nums, new Comparator<Integer>() {
        
                @Override
                public int compare(Integer o1, Integer o2) {
        
                    return o2 - o1;
                }
            });
        }
    
        public static void main(String[] args) {
        
    
            int[] arr1 = new int[]{
        5, 4, 3, 2, 1};
            System.out.print("升序排序前的arr1: ");
            for (int i = 0; i < arr1.length; i++) {
        
                System.out.print(arr1[i] + " ");
            }
            sort01(arr1);
            System.out.print("\n升序排序后的arr1: ");
            for (int i = 0; i < arr1.length; i++) {
        
                System.out.print(arr1[i] + " ");
            }
    
            int[] arr2 = new int[]{
        5, 4, 3, 2, 1};
            System.out.print("\n升序【指定了排序范围】排序前的arr2: ");
            for (int i = 0; i < arr2.length; i++) {
        
                System.out.print(arr2[i] + " ");
            }
            sort02(arr2, 1, 3);
            System.out.print("\n升序【指定了排序范围】排序后的arr2: ");
            for (int i = 0; i < arr2.length; i++) {
        
                System.out.print(arr2[i] + " ");
            }
    
            Integer[] arr3 = new Integer[]{
        1, 2, 3, 4, 5};
            System.out.print("\n降序(自带方法)排序前的arr3: ");
            for (int i = 0; i < arr3.length; i++) {
        
                System.out.print(arr3[i] + " ");
            }
            sort03(arr3);
            System.out.print("\n降序(自带方法)排序后的arr3: ");
            for (int i = 0; i < arr3.length; i++) {
        
                System.out.print(arr3[i] + " ");
            }
    
            Integer[] arr4 = new Integer[]{
        1, 2, 3, 4, 5};
            System.out.print("\n降序(重写比较器)排序前的arr4: ");
            for (int i = 0; i < arr4.length; i++) {
        
                System.out.print(arr4[i] + " ");
            }
            sort04(arr4);
            System.out.print("\n降序(重写比较器)排序后的arr4: ");
            for (int i = 0; i < arr4.length; i++) {
        
                System.out.print(arr4[i] + " ");
            }
    
        }
    
    }

![在这里插入图片描述][a4a24f9afb0b47ef864a16f6f1e5a4a8.png_pic_center]

##### 6 LeetCode - 数组 #####

[5cf7428427c34ed5abb50fd19f1ca4fb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/dcc11398790d44139a6a38cca00d1221.png
[Krahets]: https://leetcode.cn/u/jyd/
[https_www.hello-algo.com]: https://www.hello-algo.com/
[8799809ae0514e02b64444035432a969.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/7bfe42e0989d455d8aa98db4f9df6256.png
[2b70bd5a07c14c9e84de17df4f1bdd47.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/101cd812d275469da52ad8bb539a8ebb.png
[0cf3c151a675432d858679859284af67.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/e3390f3f3f0f4dd68c194d2f2d1dc943.png
[61733a98d2b34e10bdbcc9ed20304a95.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/e438b6336ced4e7fa0e9eaffe773fc0f.png
[b45c4be03b6e4d858a5ce92c5a05dbb1.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/4e54c322d3694c77b43ecba7a9948a14.png
[23800feb88e647e2b80bc088233ca22b.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/135b8baa20984867acab33aac5bb8c42.png
[1bad5a137d804d4b9bae6eacc6ae04e0.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/8897c8936e2d456caf7b79a9805112de.png
[a4a24f9afb0b47ef864a16f6f1e5a4a8.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/368c679f806a4c618129f28f81a5046b.png