文章讨论了在算法设计中如何从暴力遍历的线性时间复杂度O(m+n)优化到对数时间复杂度O(log(m+n))，通过举例二分法在寻找第K小数问题中的应用，阐述了如何通过排除一半的元素来显著减少运算次数，达到更高效的解决方案。
题目要求是要log(m+n)的时间复杂度，这样的话用暴力遍历的是m+n的复杂度，而我肯定用的暴力的方法，每次比较数组的第一个元素，分偶数还是奇数，然后循环去寻找中间的数，其实循环的次数就可以写到长度的1/2，但是这样时间复杂度是不变的（O（m+n）），这个方法很简单。但是还没有log的时间复杂度。下面的是大神的思路。
二分法的应用-查找第K小的数
他的思路就是每次去掉一半的数字，最后就剩一个数字肯定就是第K小的数字，他的多个if情况去掉了几个极端情况。很耐人寻味！
扫一扫
评论
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
查看更多评论
添加红包
