【线性表 - 数组和矩阵】

数组是一种连续存储线性结构，元素类型相同，大小相等，数组是多维的，通过使用整型索引值来访问他们的元素，数组尺寸不能改变。

• 知识点
• 数组与矩阵相关题目

  # 知识点

  数组的优点:

  • 存取速度快

    数组的缺点:

    • 事先必须知道数组的长度
    • 插入删除元素很慢
    • 空间通常是有限制的
    • 需要大块连续的内存块
    • 插入删除元素的效率很低

      # 数组与矩阵相关题目

      把数组中的 0 移到末尾

      283. Move Zeroes (Easy)在新窗口打开

      For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

      public void moveZeroes(int[] nums) {    int idx = 0;    for (int num : nums) {        if (num != 0) {            nums[idx++] = num;        }    }    while (idx  
      改变矩阵维度
       
      566. Reshape the Matrix (Easy)在新窗口打开
       
      Input:nums =[[1,2], [3,4]]r = 1, c = 4Output:[[1,2,3,4]]Explanation: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.
       
      public int[][] matrixReshape(int[][] nums, int r, int c) {    int m = nums.length, n = nums[0].length;    if (m * n != r * c) {        return nums;    }    int[][] reshapedNums = new int[r][c];    int index = 0;    for (int i = 0; i  
      找出数组中最长的连续 1
       
      485. Max Consecutive Ones (Easy)在新窗口打开
       
      public int findMaxConsecutiveOnes(int[] nums) {    int max = 0, cur = 0;    for (int x : nums) {        cur = x == 0 ? 0 : cur + 1;        max = Math.max(max, cur);    }    return max;}
       
      有序矩阵查找
       
      240. Search a 2D Matrix II (Medium)在新窗口打开
       
      [   [ 1,  5,  9],   [10, 11, 13],   [12, 13, 15]]
       
      public boolean searchMatrix(int[][] matrix, int target) {    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;    int m = matrix.length, n = matrix[0].length;    int row = 0, col = n - 1;    while (row = 0) {        if (target == matrix[row][col]) return true;        else if (target  
      有序矩阵的 Kth Element
       
      378. Kth Smallest Element in a Sorted Matrix ((Medium))在新窗口打开
       
      matrix = [  [ 1,  5,  9],  [10, 11, 13],  [12, 13, 15]],k = 8,return 13.
       
      解题参考: Share my thoughts and Clean Java Code在新窗口打开
       
      二分查找解法:
       
      public int kthSmallest(int[][] matrix, int k) {    int m = matrix.length, n = matrix[0].length;    int lo = matrix[0][0], hi = matrix[m - 1][n - 1];    while (lo