田忌赛马问题
870. 优势洗牌
给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。
返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。
思路：
给你输入两个长度相等的数组 nums1 和 nums2，请你重新组织 nums1 中元素的位置，使得 nums1 的「优势」最大化。
如果 nums1[i] > nums2[i]，就是说 nums1 在索引 i 上对 nums2[i] 有「优势」。优势最大化也就是说让你重新组织 nums1，尽可能多的让 nums1[i] > nums2[i]。
class Solution { public int[] advantageCount(int[] nums1, int[] nums2) { int n = nums1.length; // 给 nums2 降序排序 PriorityQueue<int[]> maxpq = new PriorityQueue<>( (int[] pair1, int[] pair2)->{ return pair2[1] - pair1[1]; } ); for(int i = 0; i< n; i++){ maxpq.offer(new int[]{i, nums2[i]}); } // 给 nums1 升序排序 Arrays.sort(nums1); // nums1[left] 是最小值，nums1[right] 是最大值 int left = 0, right = n - 1; int[] res = new int[n]; while (!maxpq.isEmpty()) { int[] pair = maxpq.poll(); // maxval 是 nums2 中的最大值，i 是对应索引 int i = pair[0], maxval = pair[1]; if (maxval < nums1[right]) { // 如果 nums1[right] 能胜过 maxval，那就自己上 res[i] = nums1[right]; right--; } else { // 否则用最小值混一下，养精蓄锐 res[i] = nums1[left]; left++; } } return res; } }
带权重的随机选择算法
算法框架
class Solution { // 前缀和数组 private int[] preSum; private Random rand = new Random(); public Solution(int[] w) { int n = w.length; // 构建前缀和数组，偏移一位留给 preSum[0] preSum = new int[n + 1]; preSum[0] = 0; // preSum[i] = sum(w[0..i-1]) for (int i = 1; i <= n; i++) { preSum[i] = preSum[i - 1] + w[i - 1]; } } public int pickIndex() { int n = preSum.length; // Java 的 nextInt(n) 方法在 [0, n) 中生成一个随机整数 // 再加一就是在闭区间 [1, preSum[n - 1]] 中随机选择一个数字 int target = rand.nextInt(preSum[n - 1]) + 1; // 获取 target 在前缀和数组 preSum 中的索引 // 别忘了前缀和数组 preSum 和原始数组 w 有一位索引偏移 return left_bound(preSum, target) - 1; } // 搜索左侧边界的二分搜索 private int left_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; // 搜索区间为 [left, right] while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { // 搜索区间变为 [mid+1, right] left = mid + 1; } else if (nums[mid] > target) { // 搜索区间变为 [left, mid-1] right = mid - 1; } else if (nums[mid] == target) { // 收缩右侧边界 right = mid - 1; } } // 判断 target 是否存在于 nums 中 // 此时 target 比所有数都大，返回 -1 if (left == nums.length) return -1; // 判断一下 nums[left] 是不是 target return nums[left] == target ? left : -1; } }
528. 按权重随机选择[Cisco笔试题]
给你一个 下标从 0 开始 的正整数数组 w ，其中 w[i] 代表第 i 个下标的权重。
请你实现一个函数 pickIndex ，它可以 随机地从范围 [0, w.length - 1] 内（含 0 和 w.length - 1）选出并返回一个下标。选取下标 i 的 概率 为 w[i] / sum(w) 。
- 例如，对于
w = [1, 3]，挑选下标0的概率为1 / (1 + 3) = 0.25（即，25%），而选取下标1的概率为3 / (1 + 3) = 0.75（即，75%）。
思路：
1、根据权重数组 w 生成前缀和数组 preSum。
2、生成一个取值在 preSum 之内的随机数，用二分搜索算法寻找大于等于这个随机数的最小元素索引。
3、最后对这个索引减一（因为前缀和数组有一位索引偏移），就可以作为权重数组的索引，即最终答案
前缀和数组中 0 本质上是个占位符
class Solution { private Random random = new Random(); private int[] preSum; private int n; public Solution(int[] w) { this.n = w.length; // 前缀数组，下标0就是原数组w[0] preSum = new int[n]; // 下标0就是原数组w[0] preSum[0] = w[0]; for (int i = 1; i < n; i++) { preSum[i] = preSum[i-1] + w[i]; } } public int pickIndex() { // 保证取到[1, preSum[n-1]]的闭区间 int target = random.nextInt(preSum[n-1]) + 1; // right可以从n-1开始，也可以从n开始，对结果的正确性没有影响 int left = 0, right = n; while (left < right) { int mid = left + (right - left) / 2; // 如果找到了，直接去当前的下标 if (preSum[mid] == target) { left =mid; break; } else if (preSum[mid] > target) { // 向左找，因为当前mid的值大于target，可能是"第一个大于target"的值，所以不能丢弃mid // 如果mid的值不再需要了(最终不会取到现在的mid)，那么就可以right=mid-1； right = mid; } else { // 向右找，因为当前的mid的值比target小，永远不会取到了。所以left=mid+1; left = mid + 1; } } // left代表的含义： // 当目标元素 target 不存在数组 nums 中时，搜索左侧边界的二分搜索的返回值可以做以下几种解读： // 1、返回的这个值是 nums 中大于等于 target 的最小元素索引。 // 2、返回的这个值是 target 应该插入在 nums 中的索引位置。 // 3、返回的这个值是 nums 中小于 target 的元素个数。 return left; } }
下面这道题目和上面👆一模一样
剑指 Offer II 071. 按权重生成随机数
给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。
例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。
也就是说，选取下标 i 的概率为 w[i] / sum(w) 。
class Solution { private Random random = new Random(); private int[] preSum; private int n; public Solution(int[] w) { this.n = w.length; // 前缀数组，下标0就是原数组w[0] preSum = new int[n]; // 下标0就是原数组w[0] preSum[0] = w[0]; for (int i = 1; i < n; i++) { preSum[i] = preSum[i-1] + w[i]; } } public int pickIndex() { // 保证取到[1, preSum[n-1]]的闭区间 int target = random.nextInt(preSum[n-1]) + 1; // right可以从n-1开始，也可以从n开始，对结果的正确性没有影响 int left = 0, right = n; while (left < right) { int mid = left + (right - left) / 2; // 如果找到了，直接去当前的下标 if (preSum[mid] == target) { left =mid; break; } else if (preSum[mid] > target) { // 向左找，因为当前mid的值大于target，可能是"第一个大于target"的值，所以不能丢弃mid // 如果mid的值不再需要了(最终不会取到现在的mid)，那么就可以right=mid-1； right = mid; } else { // 向右找，因为当前的mid的值比target小，永远不会取到了。所以left=mid+1; left = mid + 1; } } // left代表的含义： // 当目标元素 target 不存在数组 nums 中时，搜索左侧边界的二分搜索的返回值可以做以下几种解读： // 1、返回的这个值是 nums 中大于等于 target 的最小元素索引。 // 2、返回的这个值是 target 应该插入在 nums 中的索引位置。 // 3、返回的这个值是 nums 中小于 target 的元素个数。 return left; } }
