数据结构--数组

1 定义

1.1 数组内存结构

1.2二维数组

2 练习

2.1 将数组内两个区间内有序元素合并

2.2 leetcode88. 合并两个有序数组

3 缓存与局部性原理

1 定义

1.1 数组内存结构

1 2 3 5 6

给数组添加元素时，应将原来添加位置的元素和之后的元素进行复制

System.copy(要复制的数组，开始的位置，复制到哪个数组中去，加到数组中的哪个位置，复制的长度)

1.2二维数组

arr[i][j]

i行的索引(外层数组的索引)

j列的索引(内层数组的索引)

2 练习

2.1 将数组内两个区间内有序元素合并

思路：

可以视为两个有序区间
i和iEnd表示第一个区间 j和jEnd表示第二个区间

public class MergeTwoArrays {

    public static void main(String[] args) {
        int[] a1= {1,3,5,2,6,7};
        int[]a=new int[a1.length];
        merge(a1, 0, 2, 3,a1.length-1 , a, 0);
        System.out.println(Arrays.toString(a));
    }

    public static void merge(int[] a1,int i ,int iEnd,int j ,int jEnd,int[]a,int k) {

        // 递归的出口
        if (i>iEnd) {
            System.arraycopy(a1, j, a, k, jEnd-j+1);
            return ;
        }
        if (j>jEnd) {
            System.arraycopy(a1, i, a, k, iEnd-i+1);
            return ;
        }

        // 不断判断两个数组值的大小
        if (a1[i]<a1[j]) {
            a[k]=a1[i];
            merge(a1,i+1,iEnd,j,jEnd,a,k+1);
        }else {
            a[k]=a1[j];
            merge(a1,i,iEnd,j+1,jEnd,a,k+1);
        }
    }

2.2 leetcode88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

思路：

从数组的后边开始合并两个有序数组之所以不会覆盖尚未处理的元素，主要是因为合并的过程是逆向进行的，即从数组的末尾开始向前合并。在合并过程中，我们不断将较大的元素放入到合并后数组的末尾（即原nums1数组的末尾或之后预留的空间），而较小的元素则保留在原来的位置或稍后处理。

具体来说，我们使用了三个指针：i 指向nums1的有效元素末尾，j指向nums2的末尾，k指向合并后数组的末尾（即nums1的末尾加上nums2的长度）。在合并过程中，我们比较nums1[i]和nums2[j]的大小，将较大的元素放入nums1[k]的位置，并递减相应的指针。由于我们是从后往前合并的，所以新放入的元素总是会放在已经处理过的元素之后，因此不会覆盖尚未处理的元素。

此外，由于nums1的后半部分（即索引从m到m+n-1的部分）在合并之前已经被初始化为0（或者说是未使用的空间），这些0在合并过程中会被nums2中的元素或nums1中剩余的有效元素所替换。因此，即使我们从后往前合并，也不会影响到nums1中原本就有的有效元素（即索引从0到m-1的部分）。

总结一下，从后边合并不会覆盖尚未处理的元素的原因在于：

合并过程是逆向的，从后往前进行。
新放入的元素总是放在已经处理过的元素之后。
nums1的后半部分原本就是未使用的空间，用于存放nums2的元素或nums1中剩余的有效元素。

这种合并方法的好处在于它避免了在合并过程中进行大量的元素移动，从而提高了效率。

2 3 7 8 9 9

从前往后升序时：不断循环比较，从索引0开始，从前往后比较并将元素放在数组的前面->后面

从后往前放时：升序，最大数应该放在最后边，则从每个升序数组的末尾开始比较，将较大数放在新数组末尾

public static void  merge(int[] nums1, int m, int[] nums2, int n) {
    int i=m-1;
    int j=n-1;
    int k=m+n-1;

    while(i>=0 && j>=0 && k>=0) {
        if (nums1[i]>nums2[j]) {
            nums1[k]=nums1[i];
            k--;
            i--;
        }else {
            nums1[k]=nums2[j];
            k--;
            j--;
        }
    }
    while(j>0) {
        nums1[k]=nums2[j];
        k--;
        j--;
    }

}