算法通关村第三关|青铜|线性表数组热身

1.线性表

1.1 线性表

线性表就是具有相同特征数据元素的一个有限序列。
鱼骨头教官的线性表

1.2 数组存储元素的初始化

数组初始化时必须对从前向后的连续空间初始化，不可以出现空缺的情况。写 0 也是初始化，也要从前向后写。

2.热身-单调数组

判断是否为单调数组：

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

给定一个排序数组和一个目标值，在数组中找到目标值并返回索引，不存在就返回按顺序插入的位置：
（凡是在单调序列中查找的情况，都应该考虑是否能用二分查找提高效率）

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

3.热身-数组合并

有序数组合并：

// 找到最大的数，放到nums1的最后边
public void merge(int[] nums1, int nums1_len, int[] nums2, int num2_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] <= nums[len2]) {nums1[i--] = nums2[len2--];} else if (nums1[len1] > nums2[len2]) {nums1[i--] = nums1[len1--];}}while (len2 != -1) {nums1[i--] = nums2[len2--];}while (len1 != -1) {nums1[i--] = nums1[len1--];}
}