[leetcode 2197][Go][栈][模拟]替换数组中的非质数

题目链接

leetcode 2197 替换数组中的非质数

解题思路

拼接数组-超时

拼接数组导致每次有非质数都会将后半部分的元素遍历一遍，时间复杂度为$O(\log U * n^2)(U = max(nums))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func gcd(a int, b int) int {
	n, m := max(a, b), min(a, b)
	if m == 0 {
		return n
	}
	return gcd(m, n%m)
}

func replaceNonCoprimes(nums []int) []int {
	for i := 0; i < len(nums); i++ {
		if i > 0 {
			g := gcd(max(nums[i], nums[i-1]), min(nums[i], nums[i-1]))
			if g > 1 {
				nums[i] = (nums[i] * nums[i-1]) / g
				nums = append(nums[:i-1], nums[i:]...)
				i -= 2
			}
		}
	}
	return nums
}

数组偏移量处理

既然每次拼接字符串会超时，那就对删除元素标记成负数的遍历完后再将没有标记删除的元素一次性拼接成一个数组，为了防止需要每次向前遍历上一个未删除的元素，可以在nums[i-1]删除时将其赋值为特定负数以代表上一个未被删除元素的下标与当前下标的差值

先声明一个p，若nums[i-1]未被删除则p=i-1，若nums[i-1]被删除那p=i+nums[i-1]（此时nums[i-1]为上一个未被删除元素的偏移量）

nums[p]和nums[i]若为非互质数则将nums[p]暂时标记为-1（删除），nums[i]则为nums[p]和nums[i]的最小公倍数，再寻找p的上一个未被删除的元素下标并重新计算nums[i-1]的偏移量

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
func gcd(a int, b int) int {
	n, m := max(a, b), min(a, b)
	if m == 0 {
		return n
	}
	return gcd(m, n%m)
}

func replaceNonCoprimes(nums []int) []int {
	for i := 0; i < len(nums); i++ {
		p := -1
		if i > 0 && nums[i-1] > 0 {
			p = i - 1
		} else if i > 0 {
			p = i + nums[i-1]
		}
		if p >= 0 {
			g := gcd(max(nums[i], nums[p]), min(nums[i], nums[p]))
			if g > 1 {
				nums[i] = (nums[i] * nums[p]) / g1
                //先标记为删除
				nums[p] = -1
                //寻找p的上一个未被删除的元素
				p--
				if p >= 0 && nums[p] < 0 { 
					p += nums[p] + 1
				}
                //重新计算偏移量
				nums[i-1] = p - i
				i--
			}
		}
	}
	var ret = make([]int, 0)
	for _, n := range nums {
		if n > 0 {
			ret = append(ret, n)
		}
	}
	return ret
}

此时时间复杂度为$O(n*\log U)(U=max(nums))$

栈

计算偏移量过于复杂，当遍历完一个元素时可以直接将其下标压入栈，这样就可以直接通过出栈获取上一个元素的坐标，且同样可以做到$O(n*\log U)$

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
func gcd(a int, b int) int {
	n, m := max(a, b), min(a, b)
	if m == 0 {
		return n
	}
	return gcd(m, n%m)
}

func replaceNonCoprimes(nums []int) []int {
	var stack = linkedliststack.New()
	for i := range nums {
        //不断弹出栈直到栈空或者上一个元素和nums[i]互质
		for v, ok := stack.Pop(); ok; v, ok = stack.Pop() {
			p, _ := v.(int)
			g := gcd(nums[p], nums[i])
			if g > 1 {
				nums[i] = (nums[i] * nums[p]) / g
				nums[p] = -1
			} else {
                //若互质（未删除）则重新压入栈
				stack.Push(p)
				break
			}
		}
        //每遍历完一个元素就将其压入栈
		stack.Push(i)
	}
	var ret = make([]int, 0)
	for _, n := range nums {
		if n > 0 {
			ret = append(ret, n)
		}
	}
	return ret
}