13 篇博文 含有标签「二分查找」

1、题干​

给你一个字符串 s ，考虑其所有 重复子串 ：即 s 的（连续）子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。

返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 "" 。

示例 1：

输入：s = "banana"
输出："ana"

示例 2：

输入：s = "abcd"
输出：""

提示：

• 2 <= s.length <= 3 * 104
• s 由小写英文字母组成

卷不动了，滑动窗口交了

2、执行结果​

3、解题思路​

使用滑动窗口处理，如果当前窗口字符串长度大于已找到的最长子串长度，且在原字符串的末尾能找到另一个窗口字符串，则当前窗口字符串可以更新为最长子串；重复该动作直至窗口闭合。

• 最长重复子串记为maxStr，窗口左右边界分别记为i和j，窗口内的字符串记为curStr
• 当窗口curStr的长度大于maxStr或者右边界j越界时，窗口左边界右移i++，并移除窗口curStr起始位置的字母
• 当窗口curStr的长度不大于maxStr且右边界j未越界时
  • 在窗口curStr末尾追加右边界之后的字母s[j]，并将窗口右边界右移j++
  • 若窗口curStr的长度大于maxStr且在字符串s尾部找到另一个curStr，则更新maxStr
• 最后返回maxStr

4、代码​

var longestDupSubstring = function (s) {
  let maxStr = '',curStr = '';
  for (let i = 0, j = 0; i < s.length; i++) {
    curStr = curStr.replace(s[i - 1], '');
    while (curStr.length <= maxStr.length && j < s.length) {
      curStr += s[j], j++;
      if (curStr.length > maxStr.length && s.lastIndexOf(curStr) > i) maxStr = curStr;
    }
  }
  return maxStr;
};

5、优化​

评论区有同学表示Java和C++用这个思路会超时，可能有几个方面原因：

• 1、可能Node.js的下限比较低（受限于语言执行效率），所以Node.js能过其他不行
• 2、字符串操作方法replace和+=，Java这里应该可以用StringBuilder优化，C++不太清楚能否优化
• 3、字符串索引方法lastIndexOf没有限制边界，最坏情况下会完整遍历原字符串，但是窗口扫过的字符串实际是不需要遍历的；改成下面这样限制查找起点能快700ms~1000ms左右

 if (curStr.length > maxStr.length && s.indexOf(curStr, i + 1) > -1) maxStr = curStr;

还可以考虑手写索引方法，另外引入哈希表做缓存避免重复遍历；尝试了下，用例64（30000个v的字符串）超时，这个时候简单的缓存策略是完全失效的。

附上优化后的完整代码，只需修改 lastIndexOf 那一行

var longestDupSubstring = function (s) {
    let maxStr = '', curStr = '';
    for (let i = 0, j = 0; i < s.length; i++) {
        curStr = curStr.replace(s[i - 1], '');
        while (curStr.length <= maxStr.length && j < s.length) {
            curStr += s[j], j++;
            if (curStr.length > maxStr.length && s.indexOf(curStr, i + 1) > -1) maxStr = curStr;
        }
    }
    return maxStr;
};

整体调整，更简洁的版本：

var longestDupSubstring = function (s) {
    let maxStr = '';
    for (let i = 0, j = 0; i < s.length; i++) {
        while (j - i <= maxStr.length && j < s.length && ++j) {
            if (j - i <= maxStr.length) continue;
            const curStr = s.slice(i, j);
            if (s.indexOf(curStr, i + 1) > -1) maxStr = curStr;
        }
    }
    return maxStr;
};

1、题干​

给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干 素数  组成，且其中所有整数互不相同。

对于每对满足 0 <= i < j < arr.length 的 i 和 j ，可以得到分数 arr[i] / arr[j] 。

那么第 k 个最小的分数是多少呢?  以长度为 2 的整数数组返回你的答案, 这里 answer[0] == arr[i] 且 answer[1] == arr[j] 。

示例 1：

输入：arr = [1,2,3,5], k = 3
输出：[2,5]
解释：已构造好的分数,排序后如下所示: 
1/5, 1/3, 2/5, 1/2, 3/5, 2/3
很明显第三个最小的分数是 2/5

示例 2：

输入：arr = [1,7], k = 1
输出：[1,7]

提示：

• 2 <= arr.length <= 1000
• 1 <= arr[i] <= 3 * 104
• arr[0] == 1
• arr[i] 是一个 素数 ，i > 0
• arr 中的所有数字 互不相同 ，且按 严格递增 排序
• 1 <= k <= arr.length * (arr.length - 1) / 2

进阶：你可以设计并实现时间复杂度小于 O(n2) 的算法解决此问题吗？

2、解法1-暴力解法​

创建数组matrix，两层循环遍历素数数组，把所有素数对存入matrix中，然后对matrix进行排序。最先尝试了暴力解法，居然过了。。。

3、代码​

var kthSmallestPrimeFraction = function (arr, k) {
    const p = [];
    for (let i = 1; i < arr.length; i++) {
        for (let j = 0; j < i; j++) {
            p.push([arr[j], arr[i]]);
        }
    }

    p.sort((a, b) => a[0] / a[1] - b[0] / b[1]);

    return p[k - 1];
};

• 时间复杂度: $O(n^2*log(n^2))$
• 执行用时: 1908 ms，内存消耗: 94 MB

4、解法2-暴力解法的二分优化​

之后尝试使用二分法优化这段代码，这里二分的目标是matrix而不是原始数组arr，因为时间复杂度最高的地方在matrix的排序。优化后时间复杂度量级没有改变，但是matrix长度减半，执行速度会有所提升

思路是：

• 创建两个数组m1和m2，两层循环遍历素数数组
• 把所有商小于0.5的素数对存入m1中，其余存入m2中
• 如果k <= m1.length就对m1排序并返回m1[k-1]
• 如果k > m1.length就对m2排序并返回m2[k - m1.length - 1]

5、代码​

var kthSmallestPrimeFraction = function (arr, k) {
    const p1 = [];
    const p2 = [];
    for (let i = 1; i < arr.length; i++) {
        for (let j = 0; j < i; j++) {
            if (arr[j] / arr[i] < 0.5) {
                p1.push([arr[j], arr[i]]);
            } else {
                p2.push([arr[j], arr[i]]);
            }
        }
    }

    if (k <= p1.length) {
        p1.sort((a, b) => a[0] / a[1] - b[0] / b[1]);
        return p1[k - 1];
    } else {
        p2.sort((a, b) => a[0] / a[1] - b[0] / b[1]);
        return p2[k - p1.length - 1];
    }
};

• 时间复杂度: $O(n^2*log(n^2))$
• 执行用时: 1276 ms 内存消耗: 104.1 MB

6、解法3-桶排序​

二分方案中，把matrix二分后两个子数组的元素个数的数量级几乎相当，其实推广到$N(2<N<=n*(n-1)/2,n=1000)$也适用。也就是说matrix分成N个子组后每个子组的长度几乎相等，这其实就是桶排序。

所以如果这样理解题意就简单很多：数组中最多包含约500000（$n*(n-1)/2,n=1000$）个无序排列的小数，这些小数从0到1均匀分布，返回其中第k小的小数。

桶排序的思路：

• 创建大小为N的二维数组matrix，matrix中的每个元素(数组)就是一个桶
• 根据分组规则把所有小数均匀放入桶中
• 累计每个桶内元素数量，找到第k个小数所在的桶matrix[k']，对该桶内小数进行排序
• 在matrix[k']这个桶中找到第k个小数即可

小数的分组规则：

• 分组的关键问题是分组规则，也就是任意小数a应该放入桶的序号i是多少（即a与i之间的映射关系）
• 实际上可以用桶的数量$N$乘以小数$a$再取整作为桶的序号，即$i=Math.trunc(a*N)$，这样就建立起小数a与桶序号i的映射，消耗的时间复杂度是$O(1)$

对于这个分组规则可以举个例子：假设$N$取$1000$，对于任意小数$0.0012$，把数据代入公式$i=Math.trunc(a*N)$中算得$i=1$，也就是说$0.0012$应该放入$matrix[1]$这个桶中。

还是在暴力解法的基础上优化，只需要把matrix分为N个子数组，然后只对包含第k个小数的子数组进行排序，最后返回对应的素数对即可。

如果N的取值合适的话，时间复杂度可以降到 $O(n^2)$。这里使用的取值计算公式是：N = 10 ** Math.trunc(Math.log10(arr[arr.length - 1]))。

7、代码​

var kthSmallestPrimeFraction = function (arr, k) {
    const BASE = 10 ** Math.trunc(Math.log10(arr[arr.length - 1]));
    const matrix = new Array(BASE);
    for (let i = 1; i < arr.length; i++) {
        for (let j = 0; j < i; j++) {
            const index = Math.trunc(arr[j] / arr[i] * BASE);
            if (!matrix[index]) matrix[index] = [];
            matrix[index].push([arr[j], arr[i]]);
        }
    }

    for (let arr of matrix) {
        arr = arr || [];
        if (k - arr.length <= 0) {
            arr.sort((a, b) => a[0] / a[1] - b[0] / b[1]);
            return arr[k - 1];
        }
        k = k - arr.length;
    }
};

• 时间复杂度: $O(n^2)$
• 执行用时: 876 ms 内存消耗: 97.8 MB

8、解法4-桶排序优化​

每个桶都使用Array.push放入数据，最终只使用了其中一个桶进行排序，这在时间和空间上都存在大量浪费。可以进一步优化为，只在包含第k个小数的桶中存入素数对，其他的桶只记录元素个数即可。

程序最终逻辑：

• 计算分组数量N
• 初始化matrix并写入N个0
• 双层遍历arr，计算每个桶包含小数的数量
• 按桶累计小数数量，找到第k个小数对应的桶序号index，将桶matrix[index]赋值为空数组
• 双层遍历arr，当小数对应的序号与index相等时，将素数对放入桶matrix[index]中
• 对桶matrix[index]进行排序，返回第k个素数对

9、代码​

var kthSmallestPrimeFraction = function(arr, k) {
  // 计算分组数量N
  const N = 10 ** Math.trunc(Math.log10(arr[arr.length - 1]));
  // 初始化matrix并写入N个0
  const matrix = new Array(N).fill(0);

  // 双层遍历arr，计算每个桶包含小数的数量
  for (let i = 1; i < arr.length; i++) {
    for (let j = 0; j < i; j++) {
      const m = Math.trunc((arr[j] / arr[i]) * N);
      matrix[m] += 1;
    }
  }

  // 按桶累计小数数量，找到第k个小数对应的桶序号index，将桶`matrix[index]`赋值为空数组
  let index = 0;
  for (let i = 0; i < matrix.length; i++) {
    if (k - matrix[i] <= 0) {
      index = i;
      matrix[index] = [];
      break;
    }
    k = k - matrix[i];
  }

  // 双层遍历arr，当小数对应的序号与index相等时，将素数对放入桶`matrix[index]`中
  for (let i = 1; i < arr.length; i++) {
    for (let j = 0; j < i; j++) {
      const m = Math.trunc((arr[j] / arr[i]) * N);
      if (index === m) matrix[m].push([arr[j], arr[i]]);
    }
  }

  // 对桶`matrix[index]`进行排序，返回第k个素数对
  matrix[index].sort((a, b) => a[0] / a[1] - b[0] / b[1]);
  return matrix[index][k - 1];
};

• 时间复杂度: $O(n^2)$
• 执行用时: 92 ms 内存消耗: 41.1 MB

1、题干​

给你一个 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

示例 2：

输入：matrix = [[-5]], k = 1
输出：-5

提示：

• n == matrix.length
• n == matrix[i].length
• 1 <= n <= 300
• -109 <= matrix[i][j] <= 109
• 题目数据 保证 matrix 中的所有行和列都按 非递减顺序 排列
• 1 <= k <= n2

进阶：

• 你能否用一个恒定的内存(即 O(1) 内存复杂度)来解决这个问题?
• 你能在 O(n) 的时间复杂度下解决这个问题吗?这个方法对于面试来说可能太超前了，但是你会发现阅读这篇文章（ this paper ）很有趣。

代码​

/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(matrix, k) {
    while (matrix.length > 1) {
        const nums = [];
        const nums1 = matrix.shift();
        const nums2 = matrix.shift();

        let [k1, k2] = [0, 0];
        while (k1 < nums1.length || k2 < nums2.length) {
            if (k2 >= nums2.length || (k1 < nums1.length && nums1[k1] <= nums2[k2])) {
                nums.push(nums1[k1]);
                k1++;
                continue;
            }

            if (k1 >= nums1.length || (k2 < nums2.length && nums1[k1] > nums2[k2])) {
                nums.push(nums2[k2]);
                k2++;
            }
        }

        matrix.push(nums);
    }

    return matrix[0][k - 1];
};