算法-数组算法总结
2021-11-17 本文已影响0人
攻城老狮
数组类型总结
1 二分法
思路：前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件。写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。
1.1 在排序数组中二分查找
思路：在排序数组中查找符合某个条件的数字。数组既可能是整体排序，也可能是分段排序。一旦题目是关于排序数组并且还有查找操作，二分法总是可以尝试的。
// 704. 二分查找
// 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = left + 1;
} else {
return mid;
}
}
return -1;
}
}
// 35. 搜索插入位置
// 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
return mid;
}
}
return left;
}
}
// 34. 在排序数组中查找元素的第一个和最后一个位置
// 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[] {-1,-1};
res[0] = binarySearch(nums,target,true);
res[1] = binarySearch(nums,target,false);
return res;
}
private int binarySearch(int[] nums,int target,boolean flag) {
int res = -1;
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
res = mid;
if (flag) {
right = mid - 1;
} else {
left = mid + 1;
}
}
}
return res;
}
}
// 剑指 Offer II 068. 查找插入位置
// 给定一个排序的整数数组 nums 和一个整数目标值 target ，请在数组中找到 target ，并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0,right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
return mid;
}
}
return left;
}
}
// 剑指 Offer II 069. 山峰数组的顶部
// 符合下列属性的数组 arr 称为 山峰数组（山脉数组） ：arr.length >= 3存在 i（0 < i < arr.length - 1）使得：arr[0] < arr[1] < ... arr[i-1] < arr[i]arr[i] > arr[i+1] > ... > arr[arr.length - 1]给定由整数组成的山峰数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i ，即山峰顶部。
class Solution {
public int peakIndexInMountainArray(int[] arr) {
int left = 1,right = arr.length - 2;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (arr[mid - 1] < arr[mid] && arr[mid] > arr[mid + 1]) {
return mid;
} else if (arr[mid] > arr[mid - 1]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
// 剑指 Offer II 070. 排序数组中只出现一次的数字
// 给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。
class Solution {
public int singleNonDuplicate(int[] nums) {
int left = 0,right = nums.length / 2;
int res = -1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
int i = mid * 2;
if (i < nums.length - 1 && nums[i] == nums[i + 1]) {
left = mid + 1;
} else {
res = i;
right = mid - 1;
}
}
return nums[res];
}
}
// 剑指 Offer II 071. 按权重生成随机数
// 给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。也就是说，选取下标 i 的概率为 w[i] / sum(w) 。
class Solution {
int[] pre;
int total;
public Solution(int[] w) {
pre = new int[w.length];
pre[0] = w[0];
for (int i = 1; i < w.length; ++i) {
pre[i] = pre[i - 1] + w[i];
}
total = Arrays.stream(w).sum();
}
public int pickIndex() {
int x = (int) (Math.random() * total) + 1;
return binarySearch(x);
}
private int binarySearch(int x) {
int low = 0, high = pre.length - 1;
while (low < high) {
int mid = (high - low) / 2 + low;
if (pre[mid] < x) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
}
1.2 在数值范围内二分查找
思路：如果不知道问题的解是什么，但是知道解的范围是多少。可以尝试在这个范围内使用二分查找。关键有两点：一是确定解的范围，即解的可能最大值和最小值。二是发现中间值不是解之后如何判断接下来应该在解的范围前半部分还是后半部分查找。
// 69. Sqrt(x)
// 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。由于返回类型是整数，结果只保留 整数部分,小数部分将被舍去。
class Solution {
public int mySqrt(int x) {
int res = 0;
int left = 0;
int right = x;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if ((long) mid * mid > x) {
right = mid - 1;
} else {
res = mid;
left = mid + 1;
}
}
return res;
}
}
// 367. 有效的完全平方数
// 给定一个正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
class Solution {
public boolean isPerfectSquare(int num) {
int left = 0;
int right = num;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if ((long) mid * mid > num) {
right = mid - 1;
} else if ((long) mid * mid < num) {
left = mid + 1;
} else {
return true;
}
}
return false;
}
}
// 剑指 Offer II 072. 求平方根
// 给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。正数的平方根有两个，只输出其中的正数平方根。如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。
class Solution {
public int mySqrt(int x) {
int left = 0,right = x;
int res = -1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if ((long)mid * mid > x) {
right = mid - 1;
} else {
res = mid;
left = mid + 1;
}
}
return res;
}
}
// 剑指 Offer II 073. 狒狒吃香蕉
// 狒狒喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int max = 0;
for (int pile : piles) {
max = Math.max(max,pile);
}
int left = 1,right = max;
int res = -1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
int midH = getTime(piles,mid);
if (midH > h) {
left = mid + 1;
} else {
res = mid;
right = mid - 1;
}
}
return res;
}
private int getTime(int[] piles,int k) {
int time = 0;
for (int i = 0; i < piles.length; i++) {
time += (piles[i] + k - 1) / k;
}
return time;
}
}
2 双指针
思路：可以使用两个相反方向或者相同方向的指针扫描数组。方向相反的双指针经常用来求排序数组中的两个数字之和。方向相同的双指针通常用来求正数数组的和或者乘积。
2.1 快慢指针
思路：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
// 27. 移除元素
// 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
class Solution {
public int removeElement(int[] nums, int val) {
int slow = 0, fast = 0;
for (; fast < nums.length; fast++) {
if (nums[fast] != val) {
nums[slow++] = nums[fast];
}
}
return slow;
}
}
// 26. 删除有序数组中的重复项
// 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
class Solution {
public int removeDuplicates(int[] nums) {
int slow = 1, fast = 1;
for (; fast < nums.length; fast++) {
if (nums[fast] != nums[fast - 1]) {
nums[slow++] = nums[fast];
}
}
return slow;
}
}
// 283. 移动零
// 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
class Solution {
public void moveZeroes(int[] nums) {
int slow = 0, fast = 0;
for (; fast < nums.length; fast++) {
if (nums[fast] != 0) {
nums[slow++] = nums[fast];
}
}
while (slow < nums.length) {
nums[slow++] = 0;
}
}
}
2.2 双指针指向不同数组
思路：给定两个不同的数组，类似于比较两个数组经过某些操作处理后是否相同的题目。可以使用两个指针分别指向两个数组，经过移动来判断操作的情况。
// 844. 比较含退格的字符串
// 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。如果相等，返回 true ；否则，返回 false 。
class Solution {
public boolean backspaceCompare(String s, String t) {
return changeStr(s).equals(changeStr(t));
}
private String changeStr(String s) {
char[] arr = s.toCharArray();
int left =0, right = 0;
for (; right < arr.length; right++) {
if (arr[right] != '#' ) {
arr[left++] = arr[right];
}
if (arr[right] == '#' && left != 0) {
left--;
}
}
return String.valueOf(arr,0,left);
}
}
2.3 双端指针
思路：定义两个指针分别指向数组的两端，将其中满足条件的指针指向的内容取出并移动。之后循环再次比较两端指针内容，取出满足条件的内容。
// 977. 有序数组的平方
// 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序排序。
class Solution {
public int[] sortedSquares(int[] nums) {
int left = 0;
int right = nums.length - 1;
int[] res = new int[nums.length];
int index = res.length - 1;
while (left <= right) {
if (Math.abs(nums[left]) > Math.abs(nums[right])) {
res[index--] = nums[left] * nums[left];
left++;
} else {
res[index--] = nums[right] * nums[right];
right--;
}
}
return res;
}
}
// 剑指 Offer II 006. 排序数组中两个数字之和
// 给定一个已按照升序排列的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。
class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
while (left < right) {
if (numbers[left] + numbers[right] > target) {
right--;
} else if (numbers[left] + numbers[right] < target) {
left++;
} else {
break;
}
}
return new int[] {left,right};
}
}
// 剑指 Offer II 007. 数组中和为 0 的三个数
// 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a ，b ，c ，使得 a + b + c = 0 ？请找出所有和为 0 且 不重复 的三元组。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) break;
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int tmpNum = nums[i] + nums[left] + nums[right];
if (tmpNum > 0) {
right--;
} else if (tmpNum < 0) {
left++;
} else {
res.add(Arrays.asList(nums[i],nums[left],nums[right]));
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
}
}
return res;
}
}
3 滑动窗口
思路：所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
// 209. 长度最小的子数组
// 给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0, right = 0;
int minLen = Integer.MAX_VALUE;
int sum = 0;
for (; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
minLen = Math.min(minLen,right - left + 1);
sum -= nums[left++];
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
}
// 904. 水果成篮
// 在一排树中，第 i 棵树产生 tree[i] 型的水果。你可以从你选择的任何树开始，然后重复执行以下步骤：把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。移动到当前树右侧的下一棵树。如果右边没有树，就停下来。请注意，在选择一颗树后，你没有任何选择：你必须执行步骤 1，然后执行步骤 2，然后返回步骤 1，然后执行步骤 2，依此类推，直至停止。你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果。用这个程序你能收集的水果树的最大总量是多少？
class Solution {
public int totalFruit(int[] fruits) {
Map<Integer,Integer> map = new HashMap<>();
int left = 0, right = 0;
int maxLen = 0;
for (; right < fruits.length; right++) {
map.put(fruits[right],map.getOrDefault(fruits[right],0) + 1);
while (map.size() > 2) {
map.put(fruits[left],map.get(fruits[left]) - 1);
if (map.get(fruits[left]) == 0) {
map.remove(fruits[left]);
}
left++;
}
maxLen = Math.max(maxLen,right - left + 1);
}
return maxLen;
}
}
// 剑指 Offer II 008. 和大于等于 target 的最短子数组
// 给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0, right = 0;
int minLen = Integer.MAX_VALUE;
int sum = 0;
for (; right < nums.length; right++) {
sum += nums[right];
while (left <= right && sum >= target) {
minLen = Math.min(minLen,right - left + 1);
sum -= nums[left++];
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
}
// 剑指 Offer II 009. 乘积小于 K 的子数组
// 给定一个正整数数组 nums和整数 k ，请找出该数组内乘积小于 k 的连续的子数组的个数。
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
int res = 0;
int left = 0, right = 0;
int mul = 1;
for (; right < nums.length; right++) {
mul *= nums[right];
while (left <= right && mul >= k) {
mul /= nums[left++];
}
res += right - left + 1;
}
return res;
}
}
4 累加数组数字求子数组之和
思路：双指针解决前述问题的前提条件是所有的数字都是正数。换种思路，若需要求子数组之和，首先做预处理，计算前 i 项的和 x，若 i 项的前面有若干项的和为 x - k，则和为 k 的项数和 x - k的项数一致，累加所有符合条件的项数，便可以求得子数组之和为 k 的项数。
// 剑指 Offer II 010. 和为 k 的子数组
// 给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
map.put(0,1); //和为零的个数为1
int sum = 0, count = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
count += map.getOrDefault(sum - k,0);
map.put(sum,map.getOrDefault(sum,0) + 1);
}
return count;
}
}
// 剑指 Offer II 011. 0 和 1 个数相同的子数组
// 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
class Solution {
public int findMaxLength(int[] nums) {
Map<Integer,Integer> map = new HashMap<>();
map.put(0,-1); //和为零的位置是-1
int sum = 0, maxLen = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i] == 0 ? -1 : 1;
if (map.containsKey(sum)) {
maxLen = Math.max(maxLen,i - map.get(sum));
} else {
map.put(sum,i);
}
}
return maxLen;
}
}
5 简单模拟
思路：并不涉及到什么算法，就是模拟过程。
// 剑指 Offer II 012. 左右两边子数组的和相等
// 给你一个整数数组 nums ，请计算数组的 中心下标 。数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
class Solution {
public int pivotIndex(int[] nums) {
int total = 0;
for (int num : nums) {
total += num;
}
int leftSum = 0;
for (int i = 0; i < nums.length; i++) {
if (leftSum == total - leftSum - nums[i]) return i;
leftSum += nums[i];
}
return -1;
}
}
// 剑指 Offer II 013. 二维子矩阵的和
// 给定一个二维矩阵 matrix，以下类型的多个请求：计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
class NumMatrix {
private int[][] nums;
public NumMatrix(int[][] matrix) {
nums = new int[matrix.length + 1][matrix[0].length + 1];
for (int i = 1; i <= matrix.length; i++) {
int rowSum = 0;
for (int j = 1; j <= matrix[0].length; j++) {
rowSum += matrix[i - 1][j - 1];
nums[i][j] = nums[i - 1][j] + rowSum;
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
return nums[row2 + 1][col2 + 1] - nums[row1][col2 + 1] - nums[row2 + 1][col1] + nums[row1][col1];
}
}
// 59. 螺旋矩阵 II
class Solution {
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int total = n * n;
boolean[][] visited = new boolean[n][n];
int[][] directions = new int[][] {{0,1},{1,0},{0,-1},{-1,0}};
int directionIndex = 0;
int i = 0,j = 0;
for (int k = 1; k <= total; k++) {
res[i][j] = k;
visited[i][j] = true;
int newI = i + directions[directionIndex][0];
int newJ = j + directions[directionIndex][1];
if (newI < 0 || newI >= n || newJ < 0 || newJ >= n || visited[newI][newJ]) {
directionIndex = (directionIndex + 1) % 4;
}
i += directions[directionIndex][0];
j += directions[directionIndex][1];
}
return res;
}
}
// 54. 螺旋矩阵
// 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return res;
}
int rows = matrix.length, columns = matrix[0].length;
int total = rows * columns;
boolean[][] visited = new boolean[rows][columns];
int row = 0, column = 0;
int[][] directions = {{0,1},{1,0},{0,-1},{-1,0}};
int directionIndex = 0;
for (int i = 0; i < total; i++) {
res.add(matrix[row][column]);
visited[row][column] = true;
int newRow = row + directions[directionIndex][0];
int newColumn = column + directions[directionIndex][1];
if (newRow < 0 || newRow >= rows || newColumn < 0 || newColumn >= columns ||
visited[newRow][newColumn]) {
directionIndex = (directionIndex + 1) % 4;
}
row += directions[directionIndex][0];
column += directions[directionIndex][1];
}
return res;
}
}
