逐日算法-250409

这是我本日的算法学习纪录。

---

2187. 完成旅途的最少时间

标题形貌

思绪

   二分查找
  解题过程

为什么可以使用二分查找？
题目的关键在于探求一个最小的时间 t，使得在时间 t 内全部公交车完成的总旅途次数 sum 大于便是 totalTrips。
我们可以观察到时间的单调性：假如时间 t 内可以完成 totalTrips 次旅途，那么任何大于 t 的时间 t' 肯定也可以完成（乃至完成更多）。反之，假如时间 t 内无法完成 totalTrips 次旅途（即 sum < totalTrips），那么任何小于 t 的时间 t'' 也肯定无法完成。
这种单调性（或称为“二段性”）是使用二分查找的条件。我们可以在一个大概的时间范围内（比方从 1 到一个充足大的上限）举行二分查找。
查找目标是什么？
我们要找的是满意 sum >= totalTrips 的最小时间 t。
二分步调：

• 确定查找范围 [left, right]。left 可以是 1，right 可以是一个公道的上界，比方 min(time) * totalTrips（即假设只有最快的车在跑，完玉成部路程所需的时间）。
  
• 取中心时间 mid = left + (right - left) / 2。
  
• 盘算在 mid 时间内，全部公交车能完成的总旅途次数 sum。sum = Σ (mid / time) 对全部 i 求和。
  
• 比力 sum 和 totalTrips：
  
  
  
  • 假如 sum < totalTrips，分析 mid 时间太短，无法完成任务。真正的最短时间肯定在 mid 右侧，以是更新 left = mid + 1。
    
  • 假如 sum >= totalTrips，分析 mid 时间大概是答案，大概大概另有更短的时间也满意条件。我们须要实验更小的时间，以是更新 right = mid - 1。
    
  
  
• 循环直到 left > right。终极的 left 就是满意条件的最小时间。
  

复杂度

• 时间复杂度:                                    O                         (                         N                         log                         ⁡                         M                         )                              O(N \log M)                  O(NlogM)
  
  
  
  • 此中 N 是公交车的数目 (time.length)。
    
  • M 是二分查找的时间范围的上界。在代码中，上界设置为 min(time) * totalTrips。每次二分查找须要                                              O                               (                               N                               )                                      O(N)                        O(N) 的时间来盘算 sum 函数，二分查找本身须要                                              O                               (                               log                               ⁡                               M                               )                                      O(\log M)                        O(logM) 次迭代。
    
  
  
• 空间复杂度:                                    O                         (                         1                         )                              O(1)                  O(1)
  
  
  
  • 我们只须要常数级别的额外空间。
    
  
  

Code

1. class Solution {
2.     public long minimumTime(int[] time, int totalTrips) {
3.         long left = 1, right = Integer.MAX_VALUE;
4.         for (int x : time) {
5.             right = Math.min(right, x);
6.         }
7.         right *= totalTrips;
8.         while (left <= right) {
9.             long mid = left + (right - left) / 2;
10.             if (sum(time, mid) < totalTrips) {
11.                 left = mid + 1;
12.             } else {
13.                 right = mid - 1;
14.             }
15.         }
16.         return left;
17.     }
19.     private long sum(int[] arr, long k) {
20.         long sum = 0;
21.         for (int x : arr) {
22.             sum += (k / x);
23.         }
24.         return sum;
25.     }
26. }

复制代码

---

34. 在排序数组中查找元素的第一个和末了一个位置（复习）

标题形貌

本日是第二次写这道题，和前次相比已经明白了步调，可以完全办理题目了。
具体题解见我之前的博文：逐日算法-250405
Code

1. class Solution {
2.     public int[] searchRange(int[] nums, int target) {
3.         int left = check(nums, target);
4.         if (left == nums.length || nums[left] != target) {
5.             return new int[] {-1, -1};
6.         }
7.         int right = check(nums, target + 1) - 1;
8.         return new int[] {left, right};
9.     }
11.     private int check(int[] arr, int k) {
12.         int left = 0, right = arr.length - 1;
13.         while (left <= right) {
14.             int mid = left + (right - left) / 2;
15.             if (arr[mid] < k) {
16.                 left = mid + 1;
17.             } else {
18.                 right = mid - 1;
19.             }
20.         }
21.         return left;
22.     }
23. }

复制代码

---

2529. 正整数和负整数的最大计数（复习）

标题形貌

本日是第二次写这道题，写的已经很顺手了，就不外多表明了。
具体题解见我之前的博文：逐日算法-250406
Code

1. class Solution {
2.     public int maximumCount(int[] nums) {
3.         int neg = check(nums, 0);
4.         int pos = check(nums, 1);
5.         return Math.max(neg, (nums.length - pos));
6.     }
8.     private int check(int[] arr, int k) {
9.         int left = 0, right = arr.length - 1;
10.         while (left <= right) {
11.             int mid = left + (right - left) / 2;
12.             if (arr[mid] < k) {
13.                 left = mid + 1;
14.             } else {
15.                 right = mid - 1;
16.             }
17.         }
18.         return left;
19.     }
20. }

复制代码

---