【求队友】想去FLAG的可以试试给我讲题

insomniadog 发表于 2020-11-14 01:26:56
我来试试吧 手机打字..有啥错的明早起来改：
首先明确一个问题 二分能解的题 其题解范围一定存在单调性也就是说存在这样的区间范围都是题解 但是我们需要的只是某个最优解，下面具体分析写法：
二分不管你用

还有个就是……能不能不用反正法？
我最不能理解的就是反证法
一位fb的Phd给我讲了一个多小时这里，我都没懂😭

这不是钓鱼的么？为啥讲个题还要phd

shzhj 发表于 2020-11-14 09:08:51
这不是钓鱼的么？为啥讲个题还要phd

也可以不是啊
Phd 上岸更快啊，我只是起个辅助作用
不只是人帮我，我也在帮他们
不当伸手党，从我做起

akdhfikbk 发表于 2020-11-15 00:04
谢谢你的回复，手机打字不易，感激
我觉得道理我都懂，仍做不好所有题
以及，我看过的辅导资料，可能超乎 ...

1.
w为什么二分其实我已经给你讲了。
二分只要题解满足【单调性】即可（其实严格来说还要满足连续性，我数学不好，而且lc的题大多都是int解所以这里没有细究），即存在x0，当x>=x0时f(x)都通过，或者x<=x0时f(x)都通过，这个时候就能通过二分找到这个x0.所以其实二分也是一种“暴力”法。通常的暴力是遍历整个空间来找合适的解，但是可能会超时，二分只是利用了单调性这个特性，缩短了查找时间，（怎么缩短的？可以自己多想想）。
回到这道题，先贴我的代码：

首先，indexOf这个函数是求【任意】一个数在矩阵中的位置idx，二分是去找到满足indexof(x) >= k的最小值，即为最终答案。
[[1,10,100], [5, 15, 105]]
比如这个矩阵，想找第2小(k = 2)的元素，那么你会发现 所有x>=5的数都会满足indexof(x) >= 2，然后二分会找到最小的x，即为5

2. 第二个问题还是要回到第一个问题，其实理解了二分的过程以后就不会再问这个问题了，但是为了严谨性，下面给出证明：
设满足条件f: [indexOf(x) >= k]的最小值为x1，矩阵第k小的元素值为x2，且x1 != x2:
1. 如果x1 > x2, 因为x2是第k小的元素（即indexOf(x2) = k），所以x2 也满足条件f，x2 < x1与x1是最小值的题设相矛盾
2. 如果x1 < x2，因为矩阵第k小的元素值为x2, 那么indexOf(x1) 必定小于k，不满足条件f，矛盾
所以x1 = x2
继续用矩阵：
[[1,10,100], [5, 15, 105]]
k = 2举例，
首先，答案是5，
那么用二分答案会是4吗？不会，因为4不满足indexOf(4) >= 2这个条件
那么用二分答案会是6吗？不会，虽然6满足indexOf(6) >= 2这个条件，但是他不是满足这个条件的最小值（记住：二分只会求一个极值出来）。

看别人的东西只是帮助自己理解，楼主可以试着画图啥的，不同人讲题的方式不同不一定就能帮你懂这道题，毕竟不是每个人都是老师。

insomniadog 发表于 2020-11-15 02:09
1.
w为什么二分其实我已经给你讲了。
二分只要题解满足【单调性】即可（其实严格来说还要满足连续性， ...

谢谢你的详细解释，可我还是不懂，我觉得 咱俩都没有get到 对方的问题在哪：
首先我认为二分分为两种，一种是常规的search for sth，这个是明显二分，也就是索引范围内的二分；另外一种是值域二分，也就是不那么明显的二分，通常是需要脱掉一层马甲，或者深挖过后才发现，aha，这道题可以用值域二分来做，比如 h-index。

当x>=x0时f(x)都通过，或者x<=x0时f(x)都通过，这个时候就能通过二分找到这个x0

这个我是理解的，就是找First/last occurrence。 我不明白的是：在本题内，我们找的是什么？我的理解是：通过值域二分求中间的mid值，以此来缩紧matrix的范围。题目中需要求的是matrix中的某个值，而不是值域二分后的某个mid。值域二分过后的值，肯定在整体的取值范围内，但是不一定在matrix中。
我的问题是：为什么 你通过值域二分后得到的结果，最后一定在matrix里，并且一定是答案？
来看你的解释：
1.

indexOf这个函数是求【任意】一个数在矩阵中的位置idx，二分是去找到满足indexof(x) >= k的最小值，即为最终答案。

所以indexof(x) >= k的最小值意味着：x在矩阵中的位置 >= k的最小值？
不好意思，我没懂这是什么物理意义。k是第几小的数字，为什么和矩阵中的位置比较呢？
以及，为什么二分在这里要找最小的x?
2.
我不懂的是，为什么要求[indexOf(x) >= k]的最小值，我还是那个问题，为何最小值一定是在matrix内的？
我觉得只有在索引上面二分（而不是值域）才能找到matrix的值，从值域二分则不应定能保证最后逼近的点，就是matrix上的点，换句话说，是否在matrix上。
我的核心问题是：二分法在这里的update左右边界的条件是什么？比的到底是什么？为什么要求[indexOf(x) >= k]的最小值？以及最小值为什么一定在matrix上？

楼主可以试着画图啥的，不同人讲题的方式不同不一定就能帮你懂这道题，毕竟不是每个人都是老师。

都做了，否则不会来发帖找新大腿，众所周知，这样效率不高，而且全凭运气
以及
就我目前看过的所有题解和 解题资料，惊奇的发现，不同人讲这道题的方式 竟然出奇的一致，而且并没有一个人提过 我在above提出的这些问题，我也是很🤷‍♂️了。

不过还是谢谢，虽然我没懂的还是没懂😢

baonudesifeizha 发表于 2020-11-14 11:31:34
我这么说吧  真理解后缀自动机那种板子的人没多少 好多人过题都连蒙带猜 网络流那种以前都是做过看着差不多就往上套，您这种行为只会让您离大厂越来越远

可这是最简单的binary search呀……

我把我的原句再重写一遍：

indexOf这个函数是求【任意】一个数X在矩阵中的位置idx，
二分是去找到满足 idx>= k即indexOf(X) >= k 的最小值X0，即为最终答案。
这里的函数F(X)是indexOf(X)>=k，他的值只有true or false.

再用一遍这个例子：
[[1,10,100], [5, 15, 105]]
k = 2
现在我们如果取任意数x，用indexOf(x)都能得出一个答案


我画了下函数图，这里横坐标是x值，纵坐标是他的idx。
还是以k=2举例，
比较直觉的想法是我们去找满足K=2的，但是没办法直接这样找 ，
因为条件K=2并不是单调的，即

除了红色的区域是题解，其余区域都不满足题解，
这时候我们就要将条件转化为满足
indexOf(X) >= k的区间，
物理意义就是说我想找个数X，他在矩阵中的位置至少是第K大：

可以看出红色区域都是满足indexOf(X)>=2的数。

设F(x) 为 indexOf(X) >= 2
这个函数是单调的，即F(X)=true for X >=5, F(X) = false for X < 5.
现在我们通过二分找到了这个区间[5, INT_MAX], （其实二分只会返回一个值5，但[5, INT_MAX]都是F(x) = true的解）
那么第2个数一定是5.
为什么？
第2个数会是4吗？
不会，因为如果是4，则F(4) = true且4<5，那么我们求出的区间应该是[4,INT_MAX]
第二个数会是6吗？
不会，因为如果第二个数是6并且5<6，那么F(5)应为false，求出的区间应该[6, INT_MAX]

为什么二分在这里要找最小的x

这个不是二分“要”找最小的x，
是因为如果你用二分，你只能找到满足某个条件f(X)的最小X/最大X，（取决于你的区间是[X,MAX] 还是 [MIN,X]），
这是二分这个算法决定的。

akdhfikbk 发表于 2020-11-15 02:51
谢谢你的详细解释，可我还是不懂，我觉得 咱俩都没有get到 对方的问题在哪：
首先我认为二分分为两种， ...

我看了楼上给你的解释，觉得分析的挺到位的，说些自己的想法继续启发一下楼主。
在这道题里我们找的是什么？我们找的是使indexOf(x) >= k，并且indexOf(x-1) < k的这个x是多少；为什么二分要找最小的x，因为如果x不是最小，indexOf(x-1)就不是严格<k
为什么二分结束的时候x记为x2一定在matrix里，因为第k小的数记为x1, 一定是indexOf(x1) >= k, indexOf(x1-1) < k, 这个x1是唯一的。
我觉得楼主理解的二分按索引分按值分，这样划分是不是有点思维定式。二分的本质是利用单调性，找到x0，使满足某个条件的f(x)在x0的左侧和右侧一个是true一个是false。从这个角度去理解会不会好一点

之前做这道题和你有同样的疑问 但是看到你问了之后我刚才又想了一下 我觉得我想明白了 希望可以给你解释明白
我画了一个对应的图 并附上了我的代码

简而言之就是  你计算的mid的范围的每个数字中 -- 比如 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
                     只有matrix中存在的值 -- 即 1 5 9 10 11 12 13 15
                     对应的helper的返回值 即小于等于该值的个数count 才对应着第一个出现的count  -- 比如 1 对应着第一个1   5 对应着第一个2   9 对应着第一个3

而我的代码中的二分步骤 求出的也是出现某个k的第一个位置的数字 而每个第一个新k的位置 对应的都是matrix中的值 这也就是你的疑问所在