记录生活中的点点滴滴

0%

巧用双指针避免暴力两层for迭代

今天力扣周赛的第二题:5739. 最高频元素的频数

当时采用两层for循环进行暴力,超时了,后续看了别人的写法,利用 l r 双指针来一层for进行迭代即可,顿时恍然大悟!

还需多多积累呀!写一下这道题吧!

先看看这道题:

首先想法就是先排序,然后两层for循环,看看每一位对多能在k的范围内有多少个!

结果每次进行更新,结果res每次取res和i-j的最大值即可!

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//暴力求解
public int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
int max = 1;
for (int i = 1; i < n; i++) {
int sum = 0;
int j;
for(j=i-1;j>=0;j--){
sum+=(nums[i]-nums[j]);
if(sum>k){
break;
}
}
max = Math.max(max,i-j);
}
return max;
}

结果可想而知,测试用例如果过大,则会超出时间限制!

OK,下面换一种思路,用 l r 两个指针进行迭代,迭代r指针,不断更新l指针,这样来完成!

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//双指针解决
public int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
int sum = 0,max = 1;
for (int l=0,r=0;r<n;r++) {
sum+=nums[r];
while((r-l+1)*nums[r]-sum>k){
sum-=nums[l++];
}
max = Math.max(max,r-l+1);
}
return max;
}

OK,拿下了!