Leetcode 215:数组中的第K个最大元素

题目描述

在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

示例

示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

解题思路

偷了个懒,就是利用求第k个小的数字改的。因为求第k个大的数字和求第m个小的数字有以下关系(假设数组长度为len):m=len-k+1,所以直接进行转换即可。

代码实现

int partition(vector<int>& nums, int left, int right){ int start = left; int end = right; int poivt = nums[start]; while (start < end) { while (start < end && nums[end] >= poivt) --end; nums[start] = nums[end]; while (start < end && nums[start] < poivt) ++start; nums[end] = nums[start]; nums[start] = poivt; } return start;}int findKthLargest(vector<int>& nums, int k) { int nlen = nums.size(); int m = nlen-k+1; if (nlen < 1 || nlen < m) { return -1; } int start = 0; int end = nlen - 1; int target = 0; while (start <= end) { int mid = partition(nums, start, end); if (mid == m - 1) { target = nums[mid]; break; } else if (mid > m - 1) end = mid; else start = mid + 1; } return target;}

复杂度分析

时间复杂度:O(nlogn)

运行时间

Leetcode 221:最大正方形

题目描述

在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。

示例

输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4

解题思路

参考官方题解,步骤如下:

  1. 我们用 0 初始化另一个矩阵 dp,维数和原始矩阵维数相同;dp(i,j) 表示的是由 1 组成的最大正方形的边长。
  2. 从 (0,0)(0,0) 开始,对原始矩阵中的每一个 1,我们将当前元素的值更新为

dp(i, j)=min(dp(i−1, j), dp(i−1, j−1), dp(i, j−1))+1

  1. 我们用一个变量记录当前出现的最大边长,这样遍历一次就可以找到正方形的最大边长maxr,返回的结果就是maxr*maxr

由于动态规划可以分解为若干个独立的子问题,由于一个格子的值受其左侧、左上角和上侧三个点来决定,所以我们以四个格子举例来解释这个式子,如下图所示。我们假设左下角的格子为最小值,那么有三种情况:

  1. 该值为0。则和前面组不成正方形,dp[i]=0+1=1。
  2. 该值为1。则其它值只能大于等于1,若都是等于1,说明周围三个小正方形没办法和其它正方形组成更大的正方形,所以只能它们4个组成。
  3. 该值为大于1的数,假设为2。则代表该蓝色格子与其左侧、左上侧、上侧组成了一个边长为2的正方形,由于黑色和绿色都大于2,所以黑色格子的左上角和上侧、绿色格子的上侧都不是0,于是就可以组成一个3*3的正方形,也即边长=2+1=3。其它大小以此类推。

状态图

上面的时间复杂度为O(mn),空间复杂度为O(mn)。接下来,我们可以对其进行优化。在上面的方法中,计算第i行的dp只用到了上一个元素和第i-1行,因此我们可以使用一维dp来满足要求。在扫描一行原始矩阵元素的时候,根据公式dp[j]=min(dp[j−1],dp[j],prev)来更新dp,其中prev是dp[j-1]。对于每一行,我们执行一遍过程,最后输出最大值即可。新的方法时间复杂度为O(mn),空间复杂度为O(n)。

代码实现

int min3(int a, int b, int c){ return (a < b ? (a < c ? a : c) : (b < c ? b : c));}int maximalSquare(vector<vector<char>>& matrix) { if (matrix.empty()) return 0; int rows = matrix.size(); int cols = matrix[0].size(); vector<int> dp(cols + 1, 0); int maxr = 0, prev = 0; for (int i = 1; i <= rows; i++) { for (int j = 1; j <= cols; j++) { int temp = dp[j]; if (matrix[i - 1][j - 1] == '1') { dp[j] = min3(dp[j - 1], prev, dp[j]) + 1; maxr = max(maxr, dp[j]); } else { dp[j] = 0; } prev = temp; } } return maxr * maxr;}

复杂度分析

时间复杂度为O(mn),空间复杂度为O(n)。

运行时间