• 洗牌
  • 蓄水池
  • 加权

洗牌

大致有四种写法

  1. func shuffle(nums []int) []int {
  2.     n := len(nums)
  3.     for i := 0; i < n; i++ {
  4.         // [i, n - 1)
  5.         j := i + rand.Intn(n - i)
  6.         temp := nums[i]
  7.         nums[i] = nums[j]
  8.         nums[j] = temp
  9.     }
  10.     return nums
  11. }

主要区别在于循环条件和循环体的第一句话

  1. for i := 0; i < n -1; i++ {
  2.     j := i + rand.Intn(n-i)
  3.     // ...
  4. }
  5. for i := n -1; i >= 0; i-- {
  6.     j := rand.Intn(i)
  7.     // ...
  8. }
  9. for i := n -1; i> 0; i-- {
  10.     j := rand.Intn(i)
  11.     // ...
  12. }

那么比较下第一种与第二种的区别。 区别就是，
第一种的产生结果数量有： n (n-1) … 1
第二种产生结果数量比第一种少了最后一个 i = n-1 的时候，当 i = n-1 的时候，取值范围是 [n-1, n-1] ，所以是 n (n-1) … 2
所以两者是一样的结果。

同理，第三种第四种类比。

蓄水池

  1. func random (nums []int, k int) []int {
  2.     res := make([]int, k)
  3.     copy(res, nums)
  4.     n := len(nums)
  5.     for i:= k; i < n; i++ {
  6.         // [0, i+1) => [0, i]
  7.         j := rand.Intn(i)
  8.         if j < k {
  9.             res[j] = nums[i]
  10.         }
  11.     }
  12.     return res
  13. }

加权

  1. func searchInts(a []int, target int) int {
  2.     left, right := 0, len(a)-1
  3.     for left <= right {
  4.         mid := left + (right-left)>>1
  5.         if a[mid] >= target {
  6.             if mid == 0 || a[mid-1] < target {
  7.                 return mid
  8.             }
  9.             right = mid - 1
  10.         } else {
  11.             left = mid + 1
  12.         }
  13.     }
  14.     return -1
  15. }