LeetCode题解——数组(一)

男娘i 2023-02-23 12:25 29阅读 0赞

### 文章目录 ###

*   *  移动零
     *   *  解法
     *  重塑矩阵
     *   *  解法
     *  最大连续1的个数
     *   *  解法
     *  搜索二维矩阵 II
     *   *  解法
     *  有序矩阵中第K小的元素
     *   *  二分查找法
         *  堆排序
     *  错误的集合
     *   *  解法
     *  寻找重复数
     *   *  双指针
         *   *  推荐阅读

## 移动零 ##

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: \[0,1,0,3,12\]  
输出: \[1,3,12,0,0\]  
说明:

必须在原数组上操作，不能拷贝额外的数组。  
尽量减少操作次数。

### 解法 ###

class Solution {
        
        public void moveZeroes(int[] nums) {
        
            int index = 0;
            for (int num : nums) {
        
                if (num != 0) {
        
                    nums[index++] = num;
                }
            }
            while (index < nums.length) {
        
                nums[index++] = 0;
            }
        }
    }

## 重塑矩阵 ##

在MATLAB中，有一个非常有用的函数 reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。

给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。

重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。

如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

示例 1:
    
    输入: 
    nums = 
    [[1,2],
     [3,4]]
    r = 1, c = 4
    输出: 
    [[1,2,3,4]]
    解释:
    行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。
    示例 2:
    
    输入: 
    nums = 
    [[1,2],
     [3,4]]
    r = 2, c = 4
    输出: 
    [[1,2],
     [3,4]]
    解释:
    没有办法将 2 * 2 矩阵转化为 2 * 4 矩阵。 所以输出原矩阵。
    注意：
    
    给定矩阵的宽和高范围在 [1, 100]。
    给定的 r 和 c 都是正数。

### 解法 ###

class Solution {
        
        public int[][] matrixReshape(int[][] nums, int r, int c) {
        
            int row = nums.length, col = nums[0].length;
            if (row * col != r * c) {
        
                return nums;
            }
            int[][] res = new int[r][c];
            int index = 0;
            for (int i = 0; i < r; i++) {
        
                for (int j = 0; j < c; j++) {
        
                    res[i][j] = nums[index / col][index % col];
                    index++;
                }
            }
            return res;
        }
    }

## 最大连续1的个数 ##

[力扣链接][Link 1]

给定一个二进制数组， 计算其中最大连续1的个数。

示例 1:

输入: \[1,1,0,1,1,1\]  
输出: 3  
解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.  
注意：

输入的数组只包含 0 和1。  
输入数组的长度是正整数，且不超过 10,000。

### 解法 ###

class Solution {
        
        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;
        }
    }

## 搜索二维矩阵 II ##

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

每行的元素从左到右升序排列。  
每列的元素从上到下升序排列。

示例:
    
    现有矩阵 matrix 如下：
    
    [
      [1,   4,  7, 11, 15],
      [2,   5,  8, 12, 19],
      [3,   6,  9, 16, 22],
      [10, 13, 14, 17, 24],
      [18, 21, 23, 26, 30]
    ]
    给定 target = 5，返回 true。
    
    给定 target = 20，返回 false。

### 解法 ###

class Solution {
        
        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 < m && col >= 0) {
        
                if (matrix[row][col] == target) {
        
                    return true;
                } else if (matrix[row][col] < target) {
        
                    row++;
                } else {
        
                    col--;
                }
            }
            return false;
        }
    }

## 有序矩阵中第K小的元素 ##

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。  
请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

示例：
    
    matrix = [
       [ 1,  5,  9],
       [10, 11, 13],
       [12, 13, 15]
    ],
    k = 8,
    
    返回 13。

提示：  
你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。

### 二分查找法 ###

class Solution {
        
        public int kthSmallest(int[][] matrix, int k) {
        
            int m = matrix.length, n = matrix[0].length;
            int left = matrix[0][0], right = matrix[m - 1][n - 1];
            while (left <= right) {
        
                int mid = left + (right - left) / 2;
                int count = 0;
                for (int i = 0; i < m; i++) {
        
                    for (int j = 0; j < n && matrix[i][j] <= mid; j++) {
        
                        count++;
                    }
                }
                if (count < k) {
        
                    left = mid + 1;
                } else {
        
                    right = mid - 1;
                }
            }
            return left;
        }
    }

### 堆排序 ###

维持一个小顶堆

class Solution {
        
        public int kthSmallest(int[][] matrix, int k) {
        
            int m = matrix.length, n = matrix[0].length;
            PriorityQueue<Tuple> pq = new PriorityQueue<Tuple>();
            for (int j = 0; j < n; ++j) {
        
                pq.offer(new Tuple(0, j, matrix[0][j]));
            }
            for (int i = 0; i < k - 1; ++i) {
        
                Tuple t = pq.poll();
                if (t.x == m - 1) {
        
                    continue;
                }
                pq.offer(new Tuple(t.x + 1, t.y, matrix[t.x + 1][t.y]));
            }
            return pq.poll().val;
        }
        class Tuple implements Comparable<Tuple> {
        
            int x, y, val;
            public Tuple(int x, int y, int val) {
        
                this.x = x;
                this.y = y;
                this.val = val;
            }
            @Override
            public int compareTo(Tuple tuple) {
        
                return this.val - tuple.val;
            }
        }
    }

## 错误的集合 ##

集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。

给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

示例 1:
    
    输入: nums = [1,2,2,4]
    输出: [2,3]
    注意:
    
    给定数组的长度范围是 [2, 10000]。
    给定的数组是无序的。

### 解法 ###

class Solution {
        
        public int[] findErrorNums(int[] nums) {
        
            for (int i = 0; i < nums.length; i++) {
        
                while (nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]) {
        
                    swap(nums, i, nums[i] - 1);
                }
            }
            for (int i = 0; i < nums.length; i++) {
        
                if (nums[i] != i + 1) {
        
                    return new int[]{
        nums[i], i + 1};
                }
            }
            return null;
        }
        private void swap(int[] nums, int i, int j) {
        
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }

## 寻找重复数 ##

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:
    
    输入: [1,3,4,2,2]
    输出: 2
    示例 2:
    
    输入: [3,1,3,4,2]
    输出: 3
    说明：
    
    不能更改原数组（假设数组是只读的）。
    只能使用额外的 O(1) 的空间。
    时间复杂度小于 O(n2) 。
    数组中只有一个重复的数字，但它可能不止重复出现一次。

### 双指针 ###

把数组当成有环链表，此题变成寻找环入口。  
详细题解[https://leetcode-cn.com/problems/find-the-duplicate-number/solution/xun-zhao-zhong-fu-shu-by-leetcode-solution/][https_leetcode-cn.com_problems_find-the-duplicate-number_solution_xun-zhao-zhong-fu-shu-by-leetcode-solution]

class Solution {
        
        public int findDuplicate(int[] nums) {
        
            int slow = nums[0], fast = nums[nums[0]];
            while (slow != fast) {
        
                slow = nums[slow];
                fast = nums[nums[fast]];
            }
            fast = 0;
            while (slow != fast) {
        
                slow = nums[slow];
                fast = nums[fast];
            }
            return slow;
        }
    }

--------------------

#### 推荐阅读 ####

*  [机器学习资料汇总][Link 2]
 *  [吴恩达《机器学习》视频、作业、源码][Link 3]
 *  [106页《Python进阶》中文版正式发布][106_Python]
 *  [李航《统计学习方法》第二版完整课件][Link 4]
 *  [机器学习数学全书，1900页PDF下载][1900_PDF]

--------------------

![format_png][]

[Link 1]: https://leetcode-cn.com/problems/max-consecutive-ones/description/
[https_leetcode-cn.com_problems_find-the-duplicate-number_solution_xun-zhao-zhong-fu-shu-by-leetcode-solution]: https://leetcode-cn.com/problems/find-the-duplicate-number/solution/xun-zhao-zhong-fu-shu-by-leetcode-solution/
[Link 2]: https://mp.weixin.qq.com/s/3nOkk_Yt9D7Qp1WaWEjyZQ
[Link 3]: https://mp.weixin.qq.com/s/dErZNtBYbVA7ItPm7T_HIw
[106_Python]: https://mp.weixin.qq.com/s/_WEuuxj-QgihijjLz7NJ9g
[Link 4]: https://mp.weixin.qq.com/s/xah47OWuu8ahAUa1aFFo4Q
[1900_PDF]: https://mp.weixin.qq.com/s/9BuyhdwuHiHH3ksVUe44ZQ
[format_png]: https://imgconvert.csdnimg.cn/aHR0cDovL3dhcmRzZXB0ZW1iZXIuY2x1Yi9Gc2lzMkxhbzF6UkEtUnBic1RFREEwX3owNHdi?x-oss-process=image/format,png