排序，二分查找：求解《436. 寻找右区间》

代码算法:排序查找:二分查找语言:JavaScript 语言:Go 语言:PHP 语言:Python 语言:TypeScript 语言:Java

2022-05-20 12:01:39

排序，二分查找（Python 的 bisect.bisect_left 和 Golang 的 sort.Search），求解《436. 寻找右区间》

二分查找

Python: bisect.bisect_left(a, x, lo=0, hi=len(a))
- 在 a 中找到 x 合适的插入点以维持有序。参数 lo 和 hi 可以被用于确定需要考虑的子集
- 返回的插入点 i 可以将数组 a 分成两部分。左侧是 all(val < x for val in a[lo:i]) ，右侧是 all(val >= x for val in a[i:hi])
Golang: sort.Search(n int,f func(i int) bool) int
- 用二分查找的方法，会从[0, n)中使函数 f 为 True 的最小值
- 无法找到，返回 n

例题

436. 寻找右区间

给你一个区间数组 intervals ，其中 intervals[i] = [starti, endi] ，且每个 starti 都不同。
区间 i 的右侧区间可以记作区间 j ，并满足 startj >= endi ，且 startj 最小化。
返回一个由每个区间 i 的右侧区间的最小起始位置组成的数组。如果某个区间 i 不存在对应的右侧区间，则下标 i 处的值设为 -1 。
示例 1：
输入：intervals = [[1,2]]
输出：[-1]
解释：集合中只有一个区间，所以输出-1。

答案

双数组 · 排序

var findRightInterval = function(intervals) {
  const n = intervals.length, starts = new Array(n), ends = new Array(n), ans = new Array(n)
  for (let i = 0; i < n; i++) starts[i] = [intervals[i][0], i]
  for (let i = 0; i < n; i++) ends[i] = [intervals[i][1], i]
  starts.sort((a, b) => a[0] - b[0])
  ends.sort((a, b) => a[0] - b[0])
  for (let i = 0, j = 0; i < n; i++) {
    while (j < n && ends[i][0] > starts[j][0]) j++
    if (j < n) ans[ends[i][1]] = starts[j][1]
    else ans[ends[i][1]] = -1
  }
  return ans
};

function findRightInterval(intervals: number[][]): number[] {
  const n = intervals.length, starts = new Array(n), ends = new Array(n), ans = new Array(n)
  for (let i = 0; i < n; i++) starts[i] = [intervals[i][0], i]
  for (let i = 0; i < n; i++) ends[i] = [intervals[i][1], i]
  starts.sort((a, b) => a[0] - b[0])
  ends.sort((a, b) => a[0] - b[0])
  for (let i = 0, j = 0; i < n; i++) {
    while (j < n && ends[i][0] > starts[j][0]) j++
    if (j < n) ans[ends[i][1]] = starts[j][1]
    else ans[ends[i][1]] = -1
  }
  return ans
};


func findRightInterval(intervals [][]int) []int {
  n := len(intervals)
  starts, ends, ans := make([][2]int, n), make([][2]int, n), make([]int, n)
  for i, interval := range intervals {
    starts[i][0] = interval[0]
    starts[i][1] = i
    ends[i][0] = interval[1]
    ends[i][1] = i
  }
  sort.SliceStable(starts, func(i, j int) bool {
    return starts[i][0] < starts[j][0]
  })
  sort.SliceStable(ends, func(i, j int) bool {
    return ends[i][0] < ends[j][0]
  })
  for i, j := 0, 0; i < n; i++ {
    for j < n && ends[i][0] > starts[j][0] {
      j++
    }
    if j < n {
      ans[ends[i][1]] = starts[j][1]
    } else {
      ans[ends[i][1]] = -1
    }
  }
  return ans
}

class Solution {
  function findRightInterval($intervals) {
    $n = count($intervals);
    $starts = $ends = $ans = array_fill(0, $n, 0);
    foreach ($intervals as $i => $interval) {
      $starts[$i] = [$interval[0], $i];
      $ends[$i] = [$interval[1], $i];
    }
    usort($starts, function($a, $b) {
      return $a[0] > $b[0];
    });
    usort($ends, function($a, $b) {
      return $a[0] > $b[0];
    });
    for ($i = 0, $j = 0; $i < $n; $i++) {
      while ($j < $n && $ends[$i][0] > $starts[$j][0]) $j++;
      if ($j < $n) $ans[$ends[$i][1]] = $starts[$j][1];
      else $ans[$ends[$i][1]] = -1;
    }
    return $ans;
  }
}

class Solution:
  def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
    n = len(intervals)
    starts, ends, ans = [0] * n, [0] * n, [0] * n
    for i, interval in enumerate(intervals):
      starts[i] = [interval[0], i]
      ends[i] = [interval[1], i]
    starts.sort(key = lambda x: x[0])
    ends.sort(key = lambda x: x[0])
    j = 0
    for i in range(0, n):
      while j < n and ends[i][0] > starts[j][0]: j += 1
      if j < n: ans[ends[i][1]] = starts[j][1]
      else: ans[ends[i][1]] = -1
    return ans


class Solution {
  public int[] findRightInterval(int[][] intervals) {
    int n = intervals.length;
    int[][] starts = new int[n][2];
    int[][] ends = new int[n][2];
    int[] ans = new int[n];
    for (int i = 0; i < n; i++) {
      starts[i][0] = intervals[i][0];
      starts[i][1] = i;
      ends[i][0] = intervals[i][1];
      ends[i][1] = i;
    }
    Arrays.sort(starts, (a, b) -> a[0] - b[0]);
    Arrays.sort(ends, (a, b) -> a[0] - b[0]);
    for (int i = 0, j = 0; i < n; i++) {
      while (j < n && ends[i][0] > starts[j][0]) j++;
      if (j < n) ans[ends[i][1]] = starts[j][1];
      else ans[ends[i][1]] = -1;
    }
    return ans;
  }
}

单数组 · 二分查找

var findRightInterval = function(intervals) {
  const n = intervals.length, starts = new Array(n), ans = new Int16Array(n)
  for (let i = 0; i < n; i++) starts[i] = [intervals[i][0], i]
  starts.sort((a, b) => a[0] - b[0])
  for (let i = 0; i < n; i++) {
    let l = 0, r = n - 1
    while (l <= r) {
      const m = l + r >> 1
      if (starts[m][0] >= intervals[i][1]) r = m - 1
      else l = m + 1
    }
    ans[i] = l < n ? starts[l][1] : -1
  }
  return ans
};

function findRightInterval(intervals: number[][]): number[] {
  const n = intervals.length, starts = new Array(n), ans = new Array(n)
  for (let i = 0; i < n; i++) starts[i] = [intervals[i][0], i]
  starts.sort((a, b) => a[0] - b[0])
  for (let i = 0; i < n; i++) {
    let l = 0, r = n - 1
    while (l <= r) {
      const m = l + r >> 1
      if (starts[m][0] >= intervals[i][1]) r = m - 1
      else l = m + 1
    }
    ans[i] = l < n ? starts[l][1] : -1
  }
  return ans
};


func findRightInterval(intervals [][]int) []int {
  n := len(intervals)
  starts, ans := make([][2]int, n), make([]int, n)
  for i, interval := range intervals {
    starts[i][0] = interval[0]
    starts[i][1] = i
  }
  sort.SliceStable(starts, func(i, j int) bool {
    return starts[i][0] < starts[j][0]
  })
  for i, interval := range intervals {
    j := sort.Search(n, func(i int) bool {
      return starts[i][0] >= interval[1]
    })
    if j < n {
      ans[i] = starts[j][1]
    } else {
      ans[i] = -1
    }
  }
  return ans
}

class Solution {
  function findRightInterval($intervals) {
    $n = count($intervals);
    $starts = array_fill(0, $n, array_fill(0, 2, 0));
    foreach ($intervals as $i => $interval) {
      $starts[$i][0] = $interval[0];
      $starts[$i][1] = $i;
    }
    usort($starts, function($a, $b) {
      return $a[0] - $b[0];
    });
    foreach ($intervals as $i => $interval) {
      $l = 0;
      $r = $n - 1;
      while($l <= $r) {
        $m = $l + $r >> 1;
        if ($starts[$m][0] >= $interval[1]) $r = $m - 1;
        else $l = $m + 1;
      }
      $ans[$i] = $l < $n ? $starts[$l][1] : -1;
    }
    return $ans;
  }
}

class Solution:
  def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
    n = len(intervals)
    starts, ans = [0] * n, [-1] * n
    for i, interval in enumerate(intervals):
      starts[i] = [interval[0], i]
    starts.sort(key = lambda x : x[0])
    for i, interval in enumerate(intervals):
      j = bisect_left(starts, [interval[1]])
      if j < n: ans[i] = starts[j][1] 
    return ans

class Solution {
  public int[] findRightInterval(int[][] intervals) {
    int n = intervals.length;
    int[][] starts = new int[n][2];
    for (int i = 0; i < n; i++) {
      starts[i][0] = intervals[i][0];
      starts[i][1] = i;
    }
    Arrays.sort(starts, (a, b) -> a[0] - b[0]);
    int[] ans = new int[n];
    for (int i = 0; i < n; i++) {
      int l = 0;
      int r = n - 1;
      while (l <= r) {
        int m = l + r >> 1;
        if (starts[m][0] >= intervals[i][1]) r = m - 1;
        else l = m + 1;
      }
      ans[i] = l < n ? starts[l][1] : -1;
    }
    return ans;
  }
}

小宇

Github　力扣　 M站　全部原创，请勿转载

排序、最小值，基于排序获取中位数：求解《1887. 使数组元素相等的减少操作次数》《453. 最小操作次数使数组元素相等》和《462. 最少移动次数使数组元素相等 II》

排序、最小值，基于排序获取中位数，求解《1887. 使数组元素相等的减少操作次数》《453. 最小操作次数使数组元素相等》和《462. 最少移动次数使数组元素相等 II》

二分查找：求解《668. 乘法表中第k小的数》

二分查找，求解《668. 乘法表中第k小的数》

自定义排序：求解《937. 重新排列日志文件》

自定义排序和 Golang 的字符串分割函数，求解《937. 重新排列日志文件》