[leetcode 3347][Go][答案二分]万能的二分法

力扣随机五道题三道都是二分

题目链接

leetcode 3347 执行操作后元素的最高频率 II

解题思路

超时方案:暴力枚举+二分查找

枚举所有可能的n，再通过二分查找n的数量、n-k至n+k的范围，结合操作上限得出，在3346 执行操作后元素的最高频率 I中能通过，但在此题中能超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
func findLightIndex(nums []int, n int) int {
	var l, r = 0, len(nums) - 1
	if nums[0] >= n {
		return -1
	}
	for l < r {
		m := (l + r + 1) / 2
		if nums[m] >= n {
			r = m - 1
		} else {
			l = m
		}
	}
	return l
}

func findRightIndex(nums []int, n int) int {
	var l, r = 0, len(nums) - 1
	if nums[len(nums)-1] <= n {
		return len(nums)
	}
	for l < r {
		m := (l + r) / 2
		if nums[m] <= n {
			l = m + 1
		} else {
			r = m
		}
	}
	return r
}

func maxFrequency(nums []int, k int, numOperations int) int {
	sort.Ints(nums)
	var ret = 0
	var maxN = nums[len(arr)-1]
    var minN = nums[0]
	for n := minN; n <= maxN; n++ {
		a := findRightIndex(arr, n) - findLightIndex(arr, n) - 1
		b := findRightIndex(arr, min(maxN, n+k)) - findLightIndex(arr, max(0, n-k)) - 1
		c := a + min(b-a, numOperations)
		ret = max(ret, c)
	}
	return ret
}

答案二分

这里分出一个子问题，考虑两种情况，一是n为nums数组上的值，那么当前频率就是min([n-k,n-1]+[n+1,n+k], numOperations)+[n,n] ([a,b]代表数组上数值范围从a到b的数量)，二是n为nums数组上某些元素之间的值但不等于数组上的任何元素，那么此时频率就是min([n-k, n+k], numOperations)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//寻找第一个小于n的值的下标
func findLightIndex(nums []int, n int) int {
	if nums[0] >= n {
		return -1
	}
	return sort.Search(len(nums), func(i int) bool {
		return nums[i] >= n
	}) - 1
}
//寻找第一个大于n的值的下标
func findRightIndex(nums []int, n int) int {
	if nums[len(nums)-1] <= n {
		return len(nums)
	}
	return sort.Search(len(nums), func(i int) bool {
		return nums[i] > n
	})
}

func sub2(nums []int, k int, length int) bool {
	for i := 0; i+length <= len(nums); i++ {
		end := i + length - 1
		//只要确定左右边界差值小于等于2k就能确定中间的值一定能通过加[-k,k]得到n
		if nums[end]-nums[i] <= 2*k {
			return true
		}
	}
	return false
}


func sub1(nums []int, k int, op int) int {
	var ret = 0
	//这里主要需要计算[n,n]的长度所以需要二分查找
	for _, n := range nums {
		r1 := findRightIndex(nums, n)
		l1 := findLightIndex(nums, n)
		r2 := findRightIndex(nums, n+k)
		l2 := findLightIndex(nums, n-k)
		ret = max(ret, (r1-l1-1)+min((r2-l2-1)-(r1-l1-1), op))
	}
	return ret
}

综上所述，sub1的时间复杂度为$O(n \log n)$，sub2的时间复杂度为$O(n)$但sub1执行一次就能确定当n在nums上时的最大频率，所以主函数中只需要执行一次sub1得到m再在[m,len(nums)]范围内使用二分答案得到最大频率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func maxFrequency(nums []int, k int, numOperations int) int {
	sort.Ints(nums)
	var r1 = sub1(nums, k, numOperations)
	//查找无法满足sub2的最小length减去1即为答案
	var r2 = sort.Search(numOperations+2, func(i int) bool {
		//因为[0,r1]在sub1中已经确定所以直接返回false
		if i <= r1 {
			return false
		}
		if i > numOperations {
			return true
		}
		return !sub2(nums, k, i)
	}) - 1
	return max(r1, r2)
}