数组

这是一篇关于数组的思维导图，是程序员、算法爱好者以及计算机相关专业学生深入学习和掌握数组相关算法的实用工具。对于程序员而言，在实际开发中，数组是常用的数据结构之一，掌握各种数组算法对于解决实际问题至关重要。这张思维导图涵盖了螺旋矩阵、旋转图像、前缀和、最短无序连续子数组、除自身以外数组的乘积、合并两个有序数组、矩阵置零、轮转数组等多种典型算法。通过这张图，程序员可以快速回顾和梳理数组算法的知识体系，在遇到相关问题时能够迅速找到解题思路，提高开发效率。对于算法爱好者来说，探索和钻研不同的算法是提升编程能力和逻辑思维的有效途径。这张思维导图中的每一个算法节点都可以作为深入研究的起点，帮助他们拓展算法知识面，了解不同算法的原理和应用场景，享受算法带来的乐趣和挑战。对于计算机相关专业的学生，在学习数据结构与算法课程时，数组算法是重要的学习内容。这张思维导图可以作为辅助学习资料，帮助学生更好地理解课堂上所学的知识，将理论应用于实际的算法题目中，提升学习效果和考试成绩。

数组

• 54. 螺旋矩阵
  • class Solution { public List<Integer> spiralOrder(int[][] matrix) { List<Integer> res = new ArrayList<>(); int left = 0; int right = matrix[0].length - 1; int top = 0; int bottom = matrix.length - 1; while (true) { for (int i = left; i <= right; i++) { res.add(matrix[top][i]); } if (++top > bottom) break; for (int i = top; i <= bottom; i++) { res.add(matrix[i][right]); } if (left > --right) break; for (int i = right; i >= left; i--) { res.add(matrix[bottom][i]); } if (top > --bottom) break; for (int i = bottom; i >= top; i--) { res.add(matrix[i][left]); } if (++left > right) break; } return res; } }
• 59. 螺旋矩阵 II
  • 题目：给你一个正整数 n ，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 思路与算法： 初始化一个 n×n 大小的矩阵 mat，然后模拟整个向内环绕的填入过程： 1）定义当前左右上下边界 l,r,t,b，初始值 num = 1，迭代终止值 tar = n * n； 2）当 num <= tar 时，始终按照 从左到右 从上到下 从右到左 从下到上 填入顺序循环，每次填入后： 2.1）执行 num += 1：得到下一个需要填入的数字； 2.2）更新边界：例如从左到右填完后，上边界 t += 1，相当于上边界向内缩 1。 3）使用num <= tar而不是l < r || t < b作为迭代条件，是为了解决当n为奇数时，矩阵中心数字无法在迭代过程中被填充的问题。 4）最终返回 mat 即可。  class Solution { public int[][] generateMatrix(int n) { int[][] res = new int[n][n]; int num = 1; int l = 0; int r = n - 1; int t = 0; int b = n - 1; int target = n * n; while (num <= target) { for (int i = l; i <= r; i++) { res[t][i] = num++; } t++; for (int i = t; i <= b; i++) { res[i][r] = num++; } r--; for (int i = r; i >= l; i--) { res[b][i] = num++; } b--; for (int i = b; i >= t; i--) { res[i][l] = num++; } l++; } return res; } }
• 48. 旋转图像
  • 思路一：用翻转代替旋转 作为例子，先将其通过水平轴翻转得到：  再根据主对角线翻转得到：  就得到了答案。这是为什么呢？对于水平轴翻转而言，我们只需要枚举矩阵上半部分的元素，和下半部分的元素进行交换，即  对于主对角线翻转而言，我们只需要枚举对角线左侧的元素，和右侧的元素进行交换，即  将它们联立即可得到：  和方法一、方法二中的关键等式是一致的。 class Solution { public void rotate(int[][] matrix) { int n = matrix.length; // 水平翻转 for (int i = 0; i < n / 2; i++) { for (int j = 0; j < n; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[n - 1 - i][j]; matrix[n - 1 - i][j] = temp; } } // 主对角线翻转 for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } } }
• 前缀和
  • 560. 和为 K 的子数组
    • 使用前缀和的方法可以解决这个问题，因为我们需要找到和为k的连续子数组的个数。通过计算前缀和，我们可以将问题转化为求解两个前缀和之差等于k的情况。 假设数组的前缀和数组为prefixSum，其中prefixSum[i]表示从数组起始位置到第i个位置的元素之和。那么对于任意的两个下标i和j（i < j），如果prefixSum[j] - prefixSum[i] = k，即从第i个位置到第j个位置的元素之和等于k，那么说明从第i+1个位置到第j个位置的连续子数组的和为k。 通过遍历数组，计算每个位置的前缀和，并使用一个哈希表来存储每个前缀和出现的次数。在遍历的过程中，我们检查是否存在prefixSum[j] - k的前缀和，如果存在，说明从某个位置到当前位置的连续子数组的和为k，我们将对应的次数累加到结果中。 这样，通过遍历一次数组，我们可以统计出和为k的连续子数组的个数，并且时间复杂度为O(n)，其中n为数组的长度。 class Solution { public int subarraySum(int[] nums, int k) { int count = 0; int sum = 0; Map<Integer, Integer> map = new HashMap<>(); map.put(0, 1); for (int i = 0; i < nums.length; i++) { sum = sum + nums[i]; if (map.containsKey(sum - k)) { count = count + map.get(sum - k); } map.put(sum, map.getOrDefault(sum, 0) + 1); } return count; } }
• 581. 最短无序连续子数组(?)
  • 我们可以假设把这个数组分成三段，左段和右段是标准的升序数组，中段数组虽是无序的，但满足最小值大于左段的最大值，最大值小于右段的最小值。   class Solution { public int findUnsortedSubarray(int[] nums) { int min = nums[nums.length - 1]; int max = nums[0]; int begin = 0; int end = -1; for (int i = 0; i < nums.length; i++) { if (nums[i] < max) { end = i; } else { max = nums[i]; } } for (int i = nums.length - 1; i >= 0; i--) { if (nums[i] > min) { begin = i; } else { min = nums[i]; } } return end - begin + 1; } }
• 238. 除自身以外数组的乘积
  •  class Solution { public int[] productExceptSelf(int[] nums) { int[] answer = new int[nums.length]; answer[0] = 1; for (int i = 1; i < answer.length; i++) { answer[i] = answer[i - 1] * nums[i - 1]; } int temp = 1; for (int i = answer.length - 2; i >= 0; i--) { temp = temp * nums[i + 1]; answer[i] = answer[i] * temp; } return answer; } }
• 88. 合并两个有序数组
  • class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int num1Length = nums1.length - 1; int num1Index = m - 1; int num2Index = n - 1; while (num1Index >= 0 && num2Index >= 0) { if (nums1[num1Index] >= nums2[num2Index]) { nums1[num1Length] = nums1[num1Index]; num1Length--; num1Index--; } else { nums1[num1Length] = nums2[num2Index]; num1Length--; num2Index--; } } while (num1Index >= 0) { nums1[num1Length] = nums1[num1Index]; num1Length--; num1Index--; } while (num2Index >= 0) { nums1[num1Length] = nums2[num2Index]; num1Length--; num2Index--; } } }
• 73. 矩阵置零
  • class Solution { public void setZeroes(int[][] matrix) { int[] row = new int[matrix.length]; int[] column = new int[matrix[0].length]; for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[0].length; j++) { if (matrix[i][j] == 0) { row[i] = 1; column[j] = 1; } } } for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[0].length; j++) { if (row[i] == 1 || column[j] == 1) { matrix[i][j] = 0; } } } } }
• 189. 轮转数组
  • class Solution { public void rotate(int[] nums, int k) { k = k % nums.length; revert(nums, 0, nums.length - 1); revert(nums, 0, k - 1); revert(nums, k, nums.length - 1); } private void revert(int[] nums, int left, int right) { while (left < right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; } } }