算法通关村第三关——数组-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法通关村第三关——数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

首先要理解什么是线性表：

从语言实现的角度：

分为顺序型和链表型，顺序型就是将数据存储在一段固定的空间内，这样访问的效率很高，但是如果要删除和增加元素的话代价比较高。

而在链表型里，元素之间是通过地址依次连接的，因此访问时必须从头开始逐步向后找，因此查找效率低，而删除和增加元素非常方便。

从访问限制的角度：

栈和队列又称为访问受限的线性表，插入和删除受到了限制，只能在固定的位置进行。

从扩容的角度：

分离式结构的顺序表，要加大存储空间的时候，可以在不改变表对象的前提下对数据存储区进行扩容。

概念

数组中的元素是一个一个紧密排列的。在数组中是用索引来标记每项数据的位置。

在数组中要查找一个元素还是非常容易地。

public static int findByElement(int[] arr, int size, int key) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == key)
            return i;
    }
    return -1;
}

直接循环，如果当前的值等于要查找的元素，直接返回下标就可以了。

在数组中增加元素就有点复杂了。

public static int addByElementSequence(int[] arr, int size, int element) {
    //size和arr.length都表示元素的数量，都是从1开始编号
    if (size >= arr.length)
        return -1;
    int index = size;
    //找到新元素的插入位置
    for (int i = 0; i < size; i++) {
        if (element < arr[i]) {
            index = i;
            break;
        }
    }
    //元素后移
    for (int j = size; j > index; j--) {
        arr[j] = arr[j - 1]; //index下标开始的元素后移一个位置
    }
    arr[index] = element;//插入数据
    return index;
}

在这个代码中，int index = size这一行是我刚开始疑惑的点，后来通过调试发现，如果要插入的数据在原有数组的中间而不是首尾的时候，index会在循环中间变化，但是比如说原有数组时[1,2,3,4]，现在要插入的元素是5，那么在循环中不会对index的值发生改变，这样的花就要让index的值为size。

在这里如果要加入一个元素的话，那么后面的每个元素都需要向后移一位。

删除元素

public static int removeByElement(int[] arr, int size, int key) {
    int index = -1;
    for (int i = 0; i < size; i++) {
        if (arr[i] == key) {
            index = i;
            break;
        }
    }
    if (index != -1) {
        for (int i = index + 1; i < size; i++)
            arr[i - 1] = arr[i];
        size--;
    }
    return size;
}

一样的，先找到要删除的那个元素的下标，然后，将循环条件反过来就好了。

单调数组问题：

要看一个数组是否单调递增或者单调递减，就看它数组中的每个元素是不是后面的一个比前面的一个大或小。

public static boolean isMonotonic_2(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;
}

数组合并问题：

public void merge(int[] nums1, int nums1_len, int[] nums2, int nums2_len) {
    int i = nums1_len + nums2_len - 1;
    int len1 = nums1_len - 1, len2 = nums2_len - 1;
    while (len1 >= 0 && len2 >= 0) {
        if (nums1[len1] <= nums2[len2])
            nums1[i--] = nums2[len2--];
        else if (nums1[len1] > nums2[len2]) 
            nums1[i--] = nums1[len1--];
    }
    // 假如A或者B数组还有剩余
    while (len2 != -1) nums1[i--] = nums2[len2--];
    while (len1 != -1) nums1[i--] = nums1[len1--];
}

我要两个数组合并后的数组还是单调的，比较好的方式是从后向前插入，A和B的元素数量是固定的，所以排序后最远位置一定是A和B元素都最大的那个，依此类推，每次都找最大的那个从后向前填就可以了文章来源地址https://www.toymoban.com/news/detail-665609.html

到了这里，关于算法通关村第三关——数组的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！