LeetCode算法之数组篇

谁借莪１个温暖的怀抱￠ 2023-01-22 07:55 148阅读 0赞

练习数组算法题，得先了解数组的常用操作，只要熟悉这些操作才可以更好刷题。

## 1、预备知识 ##

**①创建数组**

Java语言中至少有四种创建数组，这里就介绍四种常用的。

int \[\] nums = \{1,3,5,7\};

int \[\] a = new int \[\]\{1,2,3,4\};

int \[\] a = new int \[4\]; //再添加

ArrayList<Integer> a = new ArrayList<>();//add添加元素

**②添加元素**

a.add(9);直接添加到数组的末尾，所以时间复杂度为**O(1)**.

a.add(1,110);//在110的位置添加1，这个是在指定位置插入元素，时间复杂度为**O(n)**.

**③访问元素**

数组直接通过索引访问，时间复杂度为**O(1)**.arr\[1\]或者**a.get(1)**

**④修改元素**

数组也是直接通过索引修改数值，**c\[1\]=1**或者**a.set(2,11)**;

**⑤删除元素**

arr.remove(元素值),**删除的时间复杂度是****O(n)**;

**⑥遍历元素**

**for循环遍历**，**时间复杂度是O(n)**;

**⑦查找元素**

对于**数组\[\]a的循环+判断**，而对于ArrayList数组可以使用**arr.contains(值)**；判断数组中是否存在。时间复杂度都是**O(n)**;

**⑧数组的长度**

数组a\[\]的获取length属性值，对于ArrayList是size()方法。

**⑨数组排序（语言的内置排序）**

数组a\[\]的使用内部**Arrays.sort(a)**;对于ArrayList则使用**Collections.sort(arr)**,他们都是默认**升序排序**，要是**降序排序**，数组a\[\]需要转为对应的包装类型数组，比如int \[\] a ---> Integer \[\] a,可以 使用Arrays.sort(arr, Comparator.reverseOrder());对arr降序排序

对于ArrayList数组可以使用**Collections.sort(arr,Collections.reverseOrder())**进行降序排序。**时间复杂度都是O(nlogn)**.

## 2、合并两个有序数组 ##

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/merge-sorted-array/][https_leetcode-cn.com_problems_merge-sorted-array]

> 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
> 
> 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素

**示例 1：**

> 输入：nums1 = \[1,2,3,0,0,0\], m = 3, nums2 = \[2,5,6\], n = 3  
> 输出：\[1,2,2,3,5,6\]

类似归并算法的最后归并。开闭空间保存。

**Java代码实现**：

class Solution {
        public void merge(int[] nums1, int m, int[] nums2, int n) {
            int i = 0;
            int j = 0;
            int count =0;
            int []temp = new int [m+n];
            while(i < m && j < n){
                if(nums1[i] > nums2[j]){
                    temp[count++]=nums2[j++];
                }else {
                    temp[count++]=nums1[i++];
                }
            }
            while(i < m){
                temp[count++] = nums1[i++];
            }
            while( j < n){
                temp[count++] = nums2[j++];
            }
            // nums1 = temp;不让过
            for(int k=0;k<nums1.length;k++){
                nums1[k]=temp[k];
            }
        }
    }

**程序运行**：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70][]

**类似的题目**可以刷 ：**寻找两个正序数组的中位数**

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/median-of-two-sorted-arrays/][https_leetcode-cn.com_problems_median-of-two-sorted-arrays]

## 3、两个数组的交集 ##

> 给定两个数组，编写一个函数来计算它们的交集。

**示例 1：**

> 输入：nums1 = \[1,2,2,1\], nums2 = \[2,2\]  
> 输出：\[2\]

**Java代码实现**：使用hashSet去除重复元素。对于**并集Java可以直接使用hashSet全部存入到hashSet中，再转为数组即可**。

class Solution {
        public int[] intersection(int[] nums1, int[] nums2) {
            Set<Integer> set1 = new HashSet<>();
            Set<Integer> set2 = new HashSet<>();
            for (int i : nums1) {
                set1.add(i);
            }
            for (int i : nums2) {
                if(set1.contains(i)){
                    set2.add(i);
                }
            }
            int [] nums3 = new int[set2.size()];
            int count=0;
            for (Integer integer : set2) {
                nums3[count++]=integer;
            }
            return nums3;
        }
    }

**程序运行**：

![20210519165511394.png][]

## 4、原地移除所有元素 ##

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/remove-element/][https_leetcode-cn.com_problems_remove-element]

> 给你一个数组 nums 和一个值 val，你需要原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
> 
> 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
> 
> 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

**示例 1：**

> 输入：nums = \[3,2,2,3\], val = 3  
> 输出：2, nums = \[2,2\]  
> 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = \[2,2,3,3\] 或 nums = \[2,2,0,0\]，也会被视作正确答案。

基本步骤：

通过一个指针index来控制，**开始指向下标索引0的位置**，不等于val就往下移动，**如果等于val不会执行任何操作，index也不会移动**。**下次再判断时就会覆盖前面的值，达到原位删除**。

**Java代码实现**：

class Solution {
        public int removeElement(int[] nums, int val) {
          int index=0;
           for(int i=0;i<nums.length;i++){
               if(nums[i]!=val){
                   nums[index] = nums[i];
                   index++;
               }
           }
           return index;
        }
    }

**程序运行**：

![20210519172412573.png][]

## 5、删除重复项 ##

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/][https_leetcode-cn.com_problems_remove-duplicates-from-sorted-array]

该题和上面的差不多意思，删除所有的重复元素需要保证**数组有序的前提**。

> 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
> 
> 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

**示例 1：**

> 输入：nums = \[1,1,2\]  
> 输出：2, nums = \[1,2\]  
> 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
> 
> 例如：分析
> 
> 1 1 4 5 6 7 8 9
> 
> 1  4 5  6  7  8  9   8 9
> 
> |<-- index值-->|

**Java代码实现**：

class Solution {
       public int removeDuplicates(int[] nums) {
           int index=1;
           for(int i=1;i<nums.length;i++){
               if(nums[i]!=nums[i-1]){
                   nums[index++]=nums[i];
               }
           }
           return index;
        }
    }

**程序运行**：

![20210519173359117.png][]

## 6、 移动零 ##

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/move-zeroes/][https_leetcode-cn.com_problems_move-zeroes]

> 给定一个数组 `nums`，编写一个函数将所有 `0` 移动到数组的末尾，同时保持非零元素的相对顺序

**示例:**

> 输入：\[0,1,0,3,12\]
> 
> 输出：\[1,3,12,0,0\]

**Java代码实现**：

class Solution {
        public void moveZeroes(int[] nums) {
            int index = 0;
           for(int i = 0;i < nums.length;i++){
               if(nums[i] != 0){
                   nums[index++] = nums[i];
               }
           }
           for( int i =index;i <nums.length; i++){
               nums[i] = 0;
           }
        }
    }

**程序运行**：

![20210519173758908.png][]

## 7、最大连续 1 的个数 ##

来源：力扣（LeetCode）  
链接：[h][https_leetcode-cn.com_problems_move-zeroes][https://leetcode-cn.com/problems/max-consecutive-ones/][https_leetcode-cn.com_problems_max-consecutive-ones]

> 给定一个二进制数组， 计算其中最大连续 1 的个数。

**示例：**

> 输入：\[1,1,0,1,1,1\]  
> 输出：3  
> 解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.

**Java代码实现**：

class Solution {
        public int findMaxConsecutiveOnes(int[] nums) {
            int count = 0;
            int result = 0;
            for(int i = 0;i < nums.length; i++){
                if(nums[i] == 1){
                    count++;
                }else {
                    result =Math.max(result,count);
                    count = 0;
                }
            }
            return Math.max(result,count);
        }
    }

## 8、唯一元素的和 ##

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/sum-of-unique-elements/][https_leetcode-cn.com_problems_sum-of-unique-elements]

> 给你一个整数数组 `nums` 。数组中唯一元素是那些只出现 **恰好一次** 的元素。
> 
> 请你返回 `nums` 中唯一元素的 **和** 。

示例：

> 输入：nums = \[1,2,3,2\]  
> 输出：4  
> 解释：唯一元素为 \[1,3\] ，和为 4 。

**Java代码实现**：

class Solution {
    public int sumOfUnique(int[] nums) {
            int sum=0;
            int [] temp = new int[101];
            for (int num : nums) {
                temp[num]++;
            }
            for(int i=0;i<temp.length;i++){
                if(temp[i]==1){
                    sum+=i;
                }
            }
            return sum;
        }
    }

[https_leetcode-cn.com_problems_merge-sorted-array]: https://leetcode-cn.com/problems/merge-sorted-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70]: /images/20221020/c74240bb4b8b4149bb5bc87f0eeea67b.png
[https_leetcode-cn.com_problems_median-of-two-sorted-arrays]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
[20210519165511394.png]: /images/20221020/1bf37823561d4e948d7bcee8b66d9a40.png
[https_leetcode-cn.com_problems_remove-element]: https://leetcode-cn.com/problems/remove-element/
[20210519172412573.png]: /images/20221020/fe2e4aed076c4011b62066678c2f5e10.png
[https_leetcode-cn.com_problems_remove-duplicates-from-sorted-array]: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
[20210519173359117.png]: /images/20221020/0069577baae6413ab3d3cb0be80646b6.png
[https_leetcode-cn.com_problems_move-zeroes]: https://leetcode-cn.com/problems/move-zeroes/
[20210519173758908.png]: /images/20221020/0b005c37e4874b458701971f5bed2a74.png
[https_leetcode-cn.com_problems_max-consecutive-ones]: https://leetcode-cn.com/problems/max-consecutive-ones/
[https_leetcode-cn.com_problems_sum-of-unique-elements]: https://leetcode-cn.com/problems/sum-of-unique-elements/