leetcode-go/hard/493.reverse-pairs.go

func reversePairs(nums []int) int {
	return mergeSort(nums, 0, len(nums)-1)
}

func mergeSort(nums []int, beg int, end int) int {
	if end <= beg {
		return 0
	}
	l, m := beg, beg+(end-beg)/2
	r, p, k := m+1, m+1, 0
	res := mergeSort(nums, beg, m) + mergeSort(nums, r, end)
	merge := make([]int, end-beg+1)
	for l <= m {
		for ; p <= end && 2*nums[p] < nums[l]; p++ {
		} // Advance l once each loop to calculate the cnt of reverse pairs
		res += p - m - 1
		for r <= end && nums[r] <= nums[l] {
			merge[k] = nums[r]
			k, r = k+1, r+1
		}
		merge[k] = nums[l]
		k, l = k+1, l+1
	}
	for r <= end {
		merge[k] = nums[r]
		k, r = k+1, r+1
	}
	copy(nums[beg:end+1], merge)
	return res
}

// ---------------------dividing line for TLE binary search algorithm---------------------

type ints [][]int

func (is ints) search(x int, beg int, end int) int {
	for beg <= end {
		mid := beg + (end-beg)/2
		if is[mid][0] < x {
			beg = mid + 1
		} else {
			end = mid - 1
		}
	}
	return beg
}

func (is *ints) insert(x int) int {
	beg, end := 0, len(*is)
	beg = is.search(2*x+1, beg, end-1)
	cnt := 0
	for i := beg; i < end; i++ {
		cnt += (*is)[i][1]
	}
	if beg == end {
		beg--
	}
	if x < 0 {
		beg = is.search(x, 0, end-1)
	} else {
		beg = is.search(x, 0, beg)
	}
	if beg == end {
		*is = append(*is, []int{x, 1})
	} else if (*is)[beg][0] == x {
		(*is)[beg][1]++
	} else {
		nis := make([][]int, end+1)
		copy(nis, (*is)[:beg])
		nis[beg] = []int{x, 1}
		copy(nis[beg+1:], (*is)[beg:])
		*is = nis
	}
	return cnt
}

func reversePairsTLE(nums []int) (cnt int) {
	var is ints = make([][]int, 0)
	for _, i := range nums {
		cnt += is.insert(i)
	}
	return
}