不简单的数组增删改查

一.线性表的结构

所谓线性表就是具有相同特征数据元素的一个有限序列,其中所含元素的个数称为线性表的长度,从不同的角度看,线性表可以有不同的分类

1.语言实现的角度:一体式与分离式

image (14)

  • 图a为一体式结构,存储表信息的单元与元素存储区以连续的方式安排在一块存储区里,两部分数据的整体形成一个完整的顺序表对象。这种结构整体性强,易于管理。但是由于数据元素存储区域是表对象的一部分,顺序表创建后,元素存储区就固定了。C和C++都是一体式的结构。
  • 图b为分离式结构,表对象里只保存与整个表有关的信息(即容量和元素个数),实际数据元素存放在另一个独立的元素存储区里,通过链接与基本表对象关联。Java和python是分离式结构。

2.储存的角度:顺序型和链表型

  • 顺序性就是将数据存放在一段固定的区间内,此时访问元素的效率非常高,但是删除和增加元素代价比较大,如果要扩容只能整体搬迁。
  • 而在链表型里,元素之间是通过地址依次连接的,因此访问时必须从头开始逐步向后找,因此查找效率低,而删除和增加元素非常方便,并且也不需要考虑扩容的问题。链表的常见实现方式又有单链表、循环链表、双向链表等等等。

3.访问限制的角度:受访问限制与不受访问限制

例如 访问限制:栈和队列,插入和删除受到了限制,只能在固定的位置进行

以下是图

image (15)

4.扩容角度

扩充的两种策略:
●第一种:每次扩充增加固定数目的存储位置,如每次扩充增加10个元素位置,这种策略可称为线性增长。特点:节省空间,但是扩充操作频繁,操作次数多。
●第二种:每次扩充容量加倍,如每次扩充增加一倍存储空间。特点:减少了扩充操作的执行次数,但可能会浪费空间资源。以空间换时间,推荐的方式。

二.数组

数组有两个需要注意的点,一个是从0开始记录,也就是第一个存元素的位置是a[0],最后一个是a[length-1]。其次,数组中的元素在内存中是连续存储的,且每个元素占用相同大小的内存

创建

int[] arr = new int[]{0,1,2,3,5,6,8};
//这么写也行:
int[] nums = {2, 5, 0, 4, 6, -10};

三.算法热身

1.单调数组问题

我们在写算法的时候,数组是否有序是一个非常重要的前提,有或者没有可能会采用完全不同的策略。 LeetCode 896.判断一个给定的数组是否为单调数组。

class Solution {
    public boolean isMonotonic(int[] nums) {
return isSort(nums,true)||isSort(nums,false);  //考虑两种情况:递增或者递减
}
public boolean isSort(int nums[],boolean increase){
    int n = nums.length;
    for(int i = 0; i<n-1;i++){
        if(increase){
            if(nums[i]>nums[i+1]){
                return false;
            }
        }else{
            if(nums[i]<nums[i+1]){
                return false;
            }
        }
    }
    return true;
}
}

优化:可以用两个变量记录一下,只要同时不满足递增和递减,则不是

public boolean isMonotonic(int[] nums) {
    boolean inc = true, dec = true;
    int n = nums.length;
    for (int i = 0; i < n - 1; ++i) {
        if (nums[i] > nums[i + 1]) {
            inc = false;
        }
        if (nums[i] < nums[i + 1]) {
            dec = false;
        }
    }
    return inc || dec;
}

2.搜索插入位置(二分查找)

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

简单来说,本题考察了对二分查找的熟悉程度,可以知道:

当tar在数组存在时,就是一个二分查找,但是不存在时,分为两种情况:

1.left与right指针相交时,两个指针此时指向由target的值决定,当target值大于mid出的值,此时left和right指向mid+1,反之指向mid-1,因此数组中不存在这种情况,只需要返回left或者right此时指向即可

class Solution {
    public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
while(left<=right){
int mid = (left+right)>>1;
if(nums[mid]==target){
    return mid;
}else if(nums[mid]>target){
    right = mid-1;
}else{
    left = mid +1;
}

}return left;
    }
}

3.数组合并专题

你两个按 非递减顺序 排列的整数数组 nums1nums2,另有两个整数 mn ,分别表示 nums1nums2 中的元素数目。

请你 合并 nums2nums1 中,使合并后的数组同样按 非递减顺序 排列。

image-20230922231938847

本题很容易想到一个做法是将数组2直接赋值给数组1的num_length+i,之后排序但是不推荐,没有亮点

public  void merge1(int[] nums1, int nums1_len, int[] nums2, int nums2_len) {
     for (int i = 0; i < nums2_len; ++i) {
         nums1[nums1_len + i] = nums2[i];
     }
     Arrays.sort(nums1);
 }

可以用一种不借助排序的方法,利用一个新数组,但是这中方案不符合题目要求,优化:

在num1的后面开始添加,然后因为是升序,需要每个数组有效元素最后一个开始从后往前遍历

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i =m-1,j=n-1;
        int len = nums1.length-1;
        while(i>=0&&j>=0){
            if(nums1[i]>nums2[j]){
                nums1[len--]=nums1[i--];
            }else{
                nums1[len--] = nums2[j--];
            }
        }
        while (len>=0){
            if(i>=0){
                nums1[len--] = nums1[i--];
            }
            if(j>=0){
                nums1[len--] = nums2[j--];
            }
        }

    }
}

优化:首先思考一个问题,当num2中为空时,此时结果是什么样?

答案是此时已经得到了结果,因为num1的长度是所有元素的数量,所以此时不需要考虑num2为空时的情况

因此只需要判断当j>=0时的情况

 int i =m-1,j=n-1;
        int len = nums1.length-1;
        while(i>=0&&j>=0){
            nums1[len--]= nums1[i]>nums2[j] ? nums1[i--]:nums2[j--];
            }
        while (j>=0){
                nums1[len--] = nums2[j--];
        }