19-二分-值域二分-有序矩阵中第 K 小的元素

这是二分法的第19篇算法,力扣链接

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

你必须找到一个内存复杂度优于 O(n2) 的解决方案。

示例 1:

输入:matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出:13
解释:矩阵中的元素为 [1,5,9,10,11,12,13,13,15],第 8 小元素是 13

 这道题很抽象,他告诉我们行和列都是有序的。但是不代表下一列一定大于上一行。

老规矩,直接上暴力法,先把所有数字存起来然后排序。

func kthSmallest(matrix [][]int, k int) int {
	nums := make([]int, len(matrix)*len(matrix[0]))
	index := 0
	for _, row := range matrix {
		for _, num := range row {
			nums[index] = num
			index++
		}
	}
	sort.Ints(nums)
	return nums[k-1]
}

那这道题二分法怎么搞呢?

首先明确,无论这个分布怎么诡异,在matrix[0][0]的数一定matrix[len(matrix)-1][len(matrix[0])-1]的数小。我门可以利用这两个值当作边界,往中间找mid,移动左右边界的逻辑可以根据小于等于mid的数的多少。当左右指针相等的时候返回指针就可以了。

这时候还会有一个疑问,当左右指针相等的时候,那个边界的值真的存在吗,这个值不是根据mid左右移动算出来的吗。

其实很简单,求出矩阵元素排序后,把矩阵分成两份,且使得前一份包含k个元素的数值范围左边界值(满足条件的数值可能是个范围,有些值不存在矩阵中,但这个左边界值一定在矩阵中)。可以尝试去推导一下,会发现这个结论是存在的。

上代码:

func kthSmallest(matrix [][]int, k int) int {
	l, r := matrix[0][0], matrix[len(matrix)-1][len(matrix[0])-1]
	for l <= r {
		mid := l + (r-l)/2
		if count(mid, matrix) < k {
			l = mid + 1
		} else {
			r = mid - 1
		}
	}
	return l
}

func count(mid int, matrix [][]int) int {
	result, x, y := 0, len(matrix)-1, 0
	for x >= 0 && y < len(matrix[0]) {
		if matrix[x][y] <= mid {
			result += x + 1
			y++
		} else {
			x--
		}
	}
	return result
}

这个count是有点学问的,这个是一列一列的加数字,梯形的方式加。

相关推荐

  1. 19-二分-值域二分-有序矩阵 K 元素

    2023-12-23 13:42:02       64 阅读
  2. 【优先队列】378. 有序矩阵 K 元素

    2023-12-23 13:42:02       50 阅读
  3. 二分查找细节

    2023-12-23 13:42:02       38 阅读
  4. 二分查找17(Leetcode1539k个缺失正整数)-2

    2023-12-23 13:42:02       54 阅读
  5. 杨氏矩阵二分查找算法实现

    2023-12-23 13:42:02       53 阅读
  6. 二分法有序数列查找元素位置

    2023-12-23 13:42:02       41 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2023-12-23 13:42:02       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2023-12-23 13:42:02       100 阅读
  3. 在Django里面运行非项目文件

    2023-12-23 13:42:02       82 阅读
  4. Python语言-面向对象

    2023-12-23 13:42:02       91 阅读

热门阅读

  1. c# opencv 提取图片文字,如读取身份证号

    2023-12-23 13:42:02       64 阅读
  2. 各大高校科研工具链培训PPT汇总

    2023-12-23 13:42:02       59 阅读
  3. 嵌入式中的定时器概念

    2023-12-23 13:42:02       69 阅读
  4. 黑苹果安装经验总结2023-12

    2023-12-23 13:42:02       101 阅读
  5. webpack之介绍

    2023-12-23 13:42:02       57 阅读
  6. cmakelists.txt中install函数/命令

    2023-12-23 13:42:02       56 阅读
  7. Unity几种移动方式

    2023-12-23 13:42:02       60 阅读
  8. 记录 | ranger修改默认文本编辑器为vim

    2023-12-23 13:42:02       58 阅读
  9. docker的应用和定义

    2023-12-23 13:42:02       52 阅读