一篇文章带你解决数组的常见基础考点

发布时间:2023-07-15 10:30

目录

      • 1、数组理论基础
      • 2、常见考点。
          • (1)、二分查找
          • (2)、移除元素

1、数组理论基础

数组是存放在连续内存空间上的相同类型数据的集合,可以通过下标索引的方式获取到下标下对应的数据。
举个栗子(字符数组)~
\"一篇文章带你解决数组的常见基础考点_第1张图片\"

可以看到:
1、数组的下标从0开始
2、数组在内存中的地址是连续的
所以在删除元素时,只能用覆盖的方式进行。
例如,要删除下标为2的元素~ 就需要将从2之后的元素依次移到前一个,覆盖掉要删除的元素。
\"一篇文章带你解决数组的常见基础考点_第2张图片\"
\"一篇文章带你解决数组的常见基础考点_第3张图片\"
\"一篇文章带你解决数组的常见基础考点_第4张图片\"
所以删除元素并不是将该元素的空间释放了,而是将后面的元素移到前面,覆盖掉要删除的元素,然后将数组的长度减去1,就能得到一个看似新的数组。
在java中,二维数组的存储方式如下:
\"一篇文章带你解决数组的常见基础考点_第5张图片\"

2、常见考点。

(1)、二分查找

力扣题目链接: 二分查找

这道题目的前提是有序数组,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的,这些都是使用二分法的前提条件。

二分查找思想是:
数组有序的前提下(假设升序),如果数组中间的值大于要查找的值,那么要查找的元素就不可能在后半部分,因为后半部分的值都大于中间的值,所以通过第一次比较,就可以将范围缩小一半,后面同理,即时间复杂度降到了O(logN),效率大大提高,当题目中要求查找元素的时间复杂度为O(logN)时,首先想一想是否能用二分呢?。

class Solution {
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
        }
        return -1;
    }
}
(2)、移除元素

有的同学可能说了,多余的元素,删掉不就得了?但是要知道数组的元素在内存地址中是连续的,不能单独删除数组中的某个元素,只能覆盖。
例如:给你一个数组和一个val值,要求删除数组中等于val值的元素,怎么做呢?
思路1:暴力法
我们可以使用两个for循环,当遍历到等于val值的元素时,就将后面的元素整体往前移一个覆盖掉要删除的元素,但是这种做法显然时间复杂度太高。

class Solution {
    public int removeElement(int[] nums, int val) {
        int size = nums.length;
        for (int i = 0; i < size;i++ ) {
            if (nums[i] == val) { // 发现需要移除的元素,就将数组后面集体向前移动一位
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; // 因为下标i以后的数值都向前移动了一位,所以i也向前移动一位
                size--;
            }
        }
        return size;
    }
}

思路2:双指针法
分别设设一个快慢指针,slow fast ,两者一起走,当慢指针遇到要删除的元素时停下,等待着被删除(覆盖);当快指针走到要被留下的元素时,将快指针的元素赋值给慢指针,然后两指针同时向后走,直到快指针遍历完整个数组。

可以这么理解:定义数组的新长度newLength ,从0开始,定义一个快指针遍历数组 fast,当fast走到要被留下的元素时,说明该元素应该被添加到新数组中(即被添加到newLength 下标,这里相当于 newLength 之前的部分数组看做要返回的新数组,相当于往这个新数组里插入元素)。

class Solution {
    public int removeElement(int[] nums, int val) {
        int fast = 0;// 定义一个快指针遍历数组
        int newLength = 0;// 定义新的数组长度
        while(fast < nums.length){
            if(nums[fast] != val){
                nums[newLength++] = nums[fast];
            }
            fast++;
        }
        return newLength;
    }
}

推荐力扣题目
1.删除排序数组中的重复项
2.移动零
3.比较含退格的字符串
4.有序数组的平方

其他常见数组的考点很多都是以这两点为基础,无非就是对数组增删改查,将数组的查找和删除掌握了,就可以开始刷题啦。

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号