ToB企服应用市场:ToB评测及商务社交产业平台

标题: 【线性表 - 数组和矩阵】 [打印本页]
作者: 大连密封材料    时间: 2024-6-22 06:23
标题: 【线性表 - 数组和矩阵】


   数组是一种连续存储线性结构，元素范例相同，巨细相称，数组是多维的，通过使用整型索引值来访问他们的元素，数组尺寸不能改变。
  
# 知识点

数组的优点:

数组的缺点:


# 数组与矩阵相关题目

把数组中的 0 移到末尾
283. Move Zeroes (Easy)在新窗口打开
  1. For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
复制代码
  1. public void moveZeroes(int[] nums) {
  2.     int idx = 0;
  3.     for (int num : nums) {
  4.         if (num != 0) {
  5.             nums[idx++] = num;
  6.         }
  7.     }
  8.     while (idx < nums.length) {
  9.         nums[idx++] = 0;
  10.     }
  11. }
复制代码
改变矩阵维度
566. Reshape the Matrix (Easy)在新窗口打开
  1. Input:
  2. nums =
  3. [[1,2],
  4. [3,4]]
  5. r = 1, c = 4
  7. Output:
  8. [[1,2,3,4]]
  10. Explanation:
  11. The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.
复制代码
  1. public int[][] matrixReshape(int[][] nums, int r, int c) {
  2.     int m = nums.length, n = nums[0].length;
  3.     if (m * n != r * c) {
  4.         return nums;
  5.     }
  6.     int[][] reshapedNums = new int[r][c];
  7.     int index = 0;
  8.     for (int i = 0; i < r; i++) {
  9.         for (int j = 0; j < c; j++) {
  10.             reshapedNums[i][j] = nums[index / n][index % n];
  11.             index++;
  12.         }
  13.     }
  14.     return reshapedNums;
  15. }
复制代码
找出数组中最长的连续 1
485. Max Consecutive Ones (Easy)在新窗口打开
  1. public int findMaxConsecutiveOnes(int[] nums) {
  2.     int max = 0, cur = 0;
  3.     for (int x : nums) {
  4.         cur = x == 0 ? 0 : cur + 1;
  5.         max = Math.max(max, cur);
  6.     }
  7.     return max;
  8. }
复制代码
有序矩阵查找
240. Search a 2D Matrix II (Medium)在新窗口打开
  1. [
  2.    [ 1,  5,  9],
  3.    [10, 11, 13],
  4.    [12, 13, 15]
  5. ]
复制代码
  1. public boolean searchMatrix(int[][] matrix, int target) {
  2.     if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
  3.     int m = matrix.length, n = matrix[0].length;
  4.     int row = 0, col = n - 1;
  5.     while (row < m && col >= 0) {
  6.         if (target == matrix[row][col]) return true;
  7.         else if (target < matrix[row][col]) col--;
  8.         else row++;
  9.     }
  10.     return false;
  11. }
复制代码
有序矩阵的 Kth Element
378. Kth Smallest Element in a Sorted Matrix ((Medium))在新窗口打开
  1. matrix = [
  2.   [ 1,  5,  9],
  3.   [10, 11, 13],
  4.   [12, 13, 15]
  5. ],
  6. k = 8,
  8. return 13.
复制代码
解题参考: Share my thoughts and Clean Java Code在新窗口打开
二分查找解法:
  1. public int kthSmallest(int[][] matrix, int k) {
  2.     int m = matrix.length, n = matrix[0].length;
  3.     int lo = matrix[0][0], hi = matrix[m - 1][n - 1];
  4.     while (lo <= hi) {
  5.         int mid = lo + (hi - lo) / 2;
  6.         int cnt = 0;
  7.         for (int i = 0; i < m; i++) {
  8.             for (int j = 0; j < n && matrix[i][j] <= mid; j++) {
  9.                 cnt++;
  10.             }
  11.         }
  12.         if (cnt < k) lo = mid + 1;
  13.         else hi = mid - 1;
  14.     }
  15.     return lo;
  16. }
复制代码
堆解法:
  1. public int kthSmallest(int[][] matrix, int k) {
  2.     int m = matrix.length, n = matrix[0].length;
  3.     PriorityQueue<Tuple> pq = new PriorityQueue<Tuple>();
  4.     for(int j = 0; j < n; j++) pq.offer(new Tuple(0, j, matrix[0][j]));
  5.     for(int i = 0; i < k - 1; i++) { // 小根堆，去掉 k - 1 个堆顶元素，此时堆顶元素就是第 k 的数
  6.         Tuple t = pq.poll();
  7.         if(t.x == m - 1) continue;
  8.         pq.offer(new Tuple(t.x + 1, t.y, matrix[t.x + 1][t.y]));
  9.     }
  10.     return pq.poll().val;
  11. }
  13. class Tuple implements Comparable<Tuple> {
  14.     int x, y, val;
  15.     public Tuple(int x, int y, int val) {
  16.         this.x = x; this.y = y; this.val = val;
  17.     }
  19.     @Override
  20.     public int compareTo(Tuple that) {
  21.         return this.val - that.val;
  22.     }
  23. }
复制代码
一个数组元素在 [1, n] 之间，此中一个数被替换为另一个数，找出重复的数和丢失的数
645. Set Mismatch (Easy)在新窗口打开
  1. Input: nums = [1,2,2,4]
  2. Output: [2,3]
复制代码
  1. Input: nums = [1,2,2,4]
  2. Output: [2,3]
复制代码
最直接的方法是先对数组举行排序，这种方法时间复杂度为 O(NlogN)。本题可以以 O(N) 的时间复杂度、O(1) 空间复杂度来求解。
重要头脑是通过交换数组元素，使得数组上的元素在精确的位置上。
  1. public int[] findErrorNums(int[] nums) {
  2.     for (int i = 0; i < nums.length; i++) {
  3.         while (nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]) {
  4.             swap(nums, i, nums[i] - 1);
  5.         }
  6.     }
  7.     for (int i = 0; i < nums.length; i++) {
  8.         if (nums[i] != i + 1) {
  9.             return new int[]{nums[i], i + 1};
  10.         }
  11.     }
  12.     return null;
  13. }
  15. private void swap(int[] nums, int i, int j) {
  16.     int tmp = nums[i];
  17.     nums[i] = nums[j];
  18.     nums[j] = tmp;
  19. }
复制代码
类似题目:

找出数组中重复的数，数组值在 [1, n] 之间
287. Find the Duplicate Number (Medium)在新窗口打开
要求不能修改数组，也不能使用额外的空间。
二分查找解法:
  1. public int findDuplicate(int[] nums) {
  2.      int l = 1, h = nums.length - 1;
  3.      while (l <= h) {
  4.          int mid = l + (h - l) / 2;
  5.          int cnt = 0;
  6.          for (int i = 0; i < nums.length; i++) {
  7.              if (nums[i] <= mid) cnt++;
  8.          }
  9.          if (cnt > mid) h = mid - 1;
  10.          else l = mid + 1;
  11.      }
  12.      return l;
  13. }
复制代码
双指针解法，类似于有环链表中找出环的入口:
  1. public int findDuplicate(int[] nums) {
  2.     int slow = nums[0], fast = nums[nums[0]];
  3.     while (slow != fast) {
  4.         slow = nums[slow];
  5.         fast = nums[nums[fast]];
  6.     }
  7.     fast = 0;
  8.     while (slow != fast) {
  9.         slow = nums[slow];
  10.         fast = nums[fast];
  11.     }
  12.     return slow;
  13. }
复制代码
数组相邻差值的个数
667. Beautiful Arrangement II (Medium)在新窗口打开
  1. Input: n = 3, k = 2
  2. Output: [1, 3, 2]
  3. Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3, and the [2, 1] has exactly 2 distinct integers: 1 and 2.
复制代码
题目形貌: 数组元素为 1~n 的整数，要求构建数组，使得相邻元素的差值不相同的个数为 k。
让前 k+1 个元素构建出 k 个不相同的差值，序列为: 1 k+1 2 k 3 k-1 ... k/2 k/2+1.
  1. public int[] constructArray(int n, int k) {
  2.     int[] ret = new int[n];
  3.     ret[0] = 1;
  4.     for (int i = 1, interval = k; i <= k; i++, interval--) {
  5.         ret[i] = i % 2 == 1 ? ret[i - 1] + interval : ret[i - 1] - interval;
  6.     }
  7.     for (int i = k + 1; i < n; i++) {
  8.         ret[i] = i + 1;
  9.     }
  10.     return ret;
  11. }
复制代码
数组的度
697. Degree of an Array (Easy)在新窗口打开
  1. Input: [1,2,2,3,1,4,2]
  2. Output: 6
复制代码
题目形貌: 数组的度定义为元素出现的最高频率，比方上面的数组度为 3。要求找到一个最小的子数组，这个子数组的度和原数组一样。
  1. public int findShortestSubArray(int[] nums) {
  2.     Map<Integer, Integer> numsCnt = new HashMap<>();
  3.     Map<Integer, Integer> numsLastIndex = new HashMap<>();
  4.     Map<Integer, Integer> numsFirstIndex = new HashMap<>();
  5.     for (int i = 0; i < nums.length; i++) {
  6.         int num = nums[i];
  7.         numsCnt.put(num, numsCnt.getOrDefault(num, 0) + 1);
  8.         numsLastIndex.put(num, i);
  9.         if (!numsFirstIndex.containsKey(num)) {
  10.             numsFirstIndex.put(num, i);
  11.         }
  12.     }
  13.     int maxCnt = 0;
  14.     for (int num : nums) {
  15.         maxCnt = Math.max(maxCnt, numsCnt.get(num));
  16.     }
  17.     int ret = nums.length;
  18.     for (int i = 0; i < nums.length; i++) {
  19.         int num = nums[i];
  20.         int cnt = numsCnt.get(num);
  21.         if (cnt != maxCnt) continue;
  22.         ret = Math.min(ret, numsLastIndex.get(num) - numsFirstIndex.get(num) + 1);
  23.     }
  24.     return ret;
  25. }
复制代码
对角元素相称的矩阵
766. Toeplitz Matrix (Easy)在新窗口打开
  1. 1234
  2. 5123
  3. 9512
  5. In the above grid, the diagonals are "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]", and in each diagonal all elements are the same, so the answer is True.
复制代码
  1. public boolean isToeplitzMatrix(int[][] matrix) {
  2.     for (int i = 0; i < matrix[0].length; i++) {
  3.         if (!check(matrix, matrix[0][i], 0, i)) {
  4.             return false;
  5.         }
  6.     }
  7.     for (int i = 0; i < matrix.length; i++) {
  8.         if (!check(matrix, matrix[i][0], i, 0)) {
  9.             return false;
  10.         }
  11.     }
  12.     return true;
  13. }
  15. private boolean check(int[][] matrix, int expectValue, int row, int col) {
  16.     if (row >= matrix.length || col >= matrix[0].length) {
  17.         return true;
  18.     }
  19.     if (matrix[row][col] != expectValue) {
  20.         return false;
  21.     }
  22.     return check(matrix, expectValue, row + 1, col + 1);
  23. }
复制代码
嵌套数组
565. Array Nesting (Medium)在新窗口打开
  1. Input: A = [5,4,0,3,1,6,2]
  2. Output: 4
  3. Explanation:
  4. A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
  6. One of the longest S[K]:
  7. S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}
复制代码
题目形貌: S 表示一个聚集，聚集的第一个元素是 A，第二个元素是 A[A]，云云嵌套下去。求最大的 S。
  1. public int arrayNesting(int[] nums) {
  2.     int max = 0;
  3.     for (int i = 0; i < nums.length; i++) {
  4.         int cnt = 0;
  5.         for (int j = i; nums[j] != -1; ) {
  6.             cnt++;
  7.             int t = nums[j];
  8.             nums[j] = -1; // 标记该位置已经被访问
  9.             j = t;
  11.         }
  12.         max = Math.max(max, cnt);
  13.     }
  14.     return max;
  15. }
复制代码
分隔数组
769. Max Chunks To Make Sorted (Medium)在新窗口打开
  1. Input: arr = [1,0,2,3,4]
  2. Output: 4
  3. Explanation:
  4. We can split into two chunks, such as [1, 0], [2, 3, 4].
  5. However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.
复制代码
题目形貌: 分隔数组，使得对每部门排序后数组就为有序。
  1. public int maxChunksToSorted(int[] arr) {
  2.     if (arr == null) return 0;
  3.     int ret = 0;
  4.     int right = arr[0];
  5.     for (int i = 0; i < arr.length; i++) {
  6.         right = Math.max(right, arr[i]);
  7.         if (right == i) ret++;
  8.     }
  9.     return ret;
  10. }
复制代码


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4