算法之旅009 - 二分搜索Level1 Day9

跟着LeetCode的Study Plan重温一遍各种经典算法，本期是二分搜索算法Level1 Day9。

题目构成：Easy*2。

1337. The K Weakest Rows in a Matrix

只有0和1组成的二维数组，每一行1都在0前面，找到1最少的前k行的行号，代码(Golang)如下：

    type Row1337 struct {
        RowNumber    int
        SoldierCount int
    }

    type RowHeap1337 []Row1337

    func (r RowHeap1337) Len() int { return len(r) }
    func (r RowHeap1337) Less(i, j int) bool {
        if r[i].SoldierCount < r[j].SoldierCount {
            return true
        }
        if r[i].SoldierCount > r[j].SoldierCount {
            return false
        }
        return r[i].RowNumber < r[j].RowNumber
    }
    func (r RowHeap1337) Swap(i, j int) { r[i], r[j] = r[j], r[i] }

    func (r *RowHeap1337) Push(x interface{}) {
        *r = append(*r, x.(Row1337))
    }

    func (r *RowHeap1337) Pop() interface{} {
        old := *r
        n := len(old)
        x := old[n-1]
        *r = old[0 : n-1]
        return x
    }

    func kWeakestRows(mat [][]int, k int) []int {
        m, n := len(mat), len(mat[0])

        rh := &RowHeap1337{}

        for i := 0; i < m; i++ {
            row := mat[i]

            j, k := 0, n-1
            for j <= k {
                p := (j + k) / 2
                v := row[p]
                if v == 0 {
                    k = p - 1
                } else {
                    j = p + 1
                }
            }
            rh.Push(Row1337{RowNumber: i, SoldierCount: k + 1})
        }
        heap.Init(rh)
        fmt.Println(rh)
        var res []int
        for i := 0; i < k; i++ {
            res = append(res, heap.Pop(rh).(Row1337).RowNumber)
        }
        return res
    }

对于任意一行，因为1都在在0前面，计算1的的个数就可以用二分搜索。然后再用各种方法保存行号和1的个数，最后输出1最少的前k行就行，这里用了heap的实现。

1346. Check If N and Its Double Exist

判断数组中是否存在一个元素是另一个元素的2倍，代码(Golang)如下：

    func checkIfExist(arr []int) bool {
        sort.Ints(arr)
        l := len(arr)
        // fmt.Println(arr)
        for i, a := range arr {
            var t int
            if a < 0 {
                if a % 2 != 0 {
                    continue
                }
                t = a / 2
            } else {
                t = a * 2
            }
            p, q := i+1, l-1
            for p <= q {
                m := (p + q) / 2
                v := arr[m]
                if v == t {
                    return true
                } else if v > t {
                    q = m - 1
                } else {
                    p = m + 1
                }
            }
        }
        return false
    }

这道题可以直接用map简单快速实现，但如果用二分可以不占用额外空间，时间更慢一点：
1. 首先对数组排序
2. 遍历每一个元素a，如果a >= 0，使用二分搜索查找t = a * 2是否在数组后面，避免直接对整个数组进行二分
3. 如果a < 0，则查找t = a / 2是否在数组后面