实验室暑假学习第一周算法总结

女爷i 2023-02-27 05:45 11阅读 0赞

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

**难度** 中等

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

**示例**

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

**提示**  
你可以假设 k 的值永远是有效的，`1 ≤ k ≤ n²`。

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

**解法一** 将矩阵转化为一维数组并排序  
语言：Python 3

class Solution:
        def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
            matrix = [i for j in matrix for i in j]
            matrix = sorted(matrix)
            return matrix[k - 1]

**解法二** 二分查找法  
语言：C

int kthSmallest(int** matrix, int matrixSize, int* matrixColSize, int k) { 
        int left = matrix[0][0], right = matrix[matrixSize - 1][matrixSize - 1];
        while (left < right) { 
            int mid = left + (right - left) / 2;
            if (check(matrix, matrixSize, mid, k)) { 
                left = mid + 1;
            } else { 
                right = mid;
            }
        }
        return left;
    }
    
    int check(int** matrix, int matrixSize, int mid, int k) { 
        int num = 0;
        int i = matrixSize - 1, j = 0;
        while (i >= 0 && j < matrixSize) { 
            if (matrix[i][j] <= mid) { 
                j++;
                num += i + 1;
            } else { 
                i--;
            }
            if (num >= k)
                return 0;
        }
        return 1;
    }

依据题意，矩阵里的元素是自左上至右下递增的，即`matrix[0][0]`为最小值，记为`left`，`matrix[n-1][n-1]`为最大值，记为`right`。这样，所要查找的元素`x`必定满足`left ≤ x ≤ right`。  
与此同时，我们可以发现，任取一个数`mid`，`mid`满足`left ≤ mid ≤ right`，都有如下性质：矩阵中不大于`mid`的数全部分布在矩阵的左上角，大于`mid`的数全部分布在矩阵的右下角。  
下面借用一下LeetCode官方题解给出的图来帮助理解，取`mid = 8`，则矩阵被一条锯齿线分为左上和右下两个部分。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70]  
将起始位置设置为`matrix[n-1][0]`，初始化计数变量`num = 0`，设当前位置为`matrix[i][j]`。若`matrix[i][j] ≤ mid`，则将当前所在列的不大于`mid`的数的数量（即`i + 1`）累加到计数变量`num`中，并向右移动（即`j`自加1）；否则，向上移动（即`i`自减1）。这样，只需要自下而上地沿着锯齿线走一遍，即可统计出矩阵中有多少个数字不大于`mid`了。  
计算矩阵中有多少数不大于`mid`，若数量不小于`k`，则所要查找的元素`x`不大于`mid`；若数量小于`k`，则所要查找的元素`x`大于`mid`。二分查找结束后，即可找出`x`。

## LeetCode 697. 数组的度 ##

**难度** 简单

给定一个非空且只包含非负数的整数数组`nums`，数组的度的定义是指数组里任一元素出现频数的最大值。  
你的任务是找到与`nums`拥有相同大小的度的最短连续子数组，返回其长度。

**示例1**

输入: [1, 2, 2, 3, 1]
    输出: 2
    解释: 
    输入数组的度是2，因为元素1和2的出现频数最大，均为2.
    连续子数组里面拥有相同度的有如下所示:
    [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
    最短连续子数组[2, 2]的长度为2，所以返回2.

**示例2**

输入: [1,2,2,3,1,4,2]
    输出: 6

**注意**  
`nums.length`在1到50,000区间范围内。  
`nums[i]`是一个在0到49,999范围内的整数。

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

**解法** HashMap  
语言：C

int findShortestSubArray(int* nums, int numsSize) { 
        int count[50000] = { 0};
        int left[50000] = { 0};
        int right[50000] = { 0};
        int degree = 0;                             /* 初始化数组的度 */
        int min = numsSize;                         /* 初始化最短连续子数组的长度 */
        for (int i = 0; i < numsSize; i++) { 
            count[nums[i]]++;
            if (count[nums[i]] == 1)                /* 首次出现记录左值 */
                left[nums[i]] = i;
            right[nums[i]] = i;                     /* 记录右值 */
            if (count[nums[i]] > degree)            /* 记录数组的度 */
                degree = count[nums[i]];
        }
        for (int i = 0; i < numsSize; i++)
            if (count[nums[i]] == degree)
                min = right[nums[i]] - left[nums[i]] + 1 < min ? (right[nums[i]] - left[nums[i]] + 1) : min;
        return min;
    }

首先定义三个数组`count`, `left`, `right`。其中`count`的作用是计数，以给定数组`nums`的元素`nums[i]`作为下标，其对应的元素值即为`nums[i]`的值在数组`nums`中出现的次数。`left`和`right`分别记录`nums[i]`的值第一次出现和最后一次出现时所对应的下标`i`，我将其称之为元素`nums[i]`对应的的左值和右值。接下来初始化数组的度`degree = 0`，初始化最短连续子数组的长度`min = numsSize`。  
对`nums`数组进行遍历，记录每个元素出现的次数和其对应的左右值。在记录左右值的时候要注意，如果某个元素是第一次记录，则要记录左值和右值；否则，只刷新右值即可，左值不需要更改。每遍历完一个元素，刷新一次数组的度，即如果`count[nums[i]] > degree`，令`degree = count[nums[i]]`。  
最后，遍历`count`数组，如果`count[nums[i]]`与`degree`相等，则取`right[nums[i]] - left[nums[i]] + 1`和`min`的较小者赋值给`min`。这样，完全遍历`count`之后得到的`min`即为本题所求。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70]: /images/20230209/e9817b9166484595b3a7be395f10543a.png