全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。
真题库：https://www.yuque.com/codernav.com/od
题目：优雅数组
知识点双指针数组滑窗
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
如果一个数组中出现次数最多的元素出现大于等于k次，被称为`k-优雅数组`，k也可以被称为`优雅阈值`。
例如，数组`[1, 2, 3, 1, 2, 3, 1]`，它是一个`3-优雅数组`，因为元素`1`出现次数大于等于3次，数组`[1, 2, 3, 1, 2]`就不是一个`3-优雅数组`，因为其中出现次数最多的元素时`1`和`2`，只出现了2次。
给定一个数组A和k，请求出A有多少子数组是`k-优雅子数组`。
子数组是数组中一个或多个连续元素组成的数组。
例如，数组`[1, 2, 3, 4]`包含10个子数组，分别是：`[1]`，`[1, 2]`，`[1, 2, 3]`，`[1, 2, 3, 4]`，`[2]`，`[2, 3]`，`[2, 3, 4]`，`[3]`，`[3, 4]`，`[4]`。
输入描述：
第一行输入两个整数n和k，n是数组A的长度，k是优雅阈值。
第二行输入n个整数，表示给定的数组A。
1 <= n <= 10000, 1 <= k <= n
数组A中的元素A[i]满足：1 <= A[i] <= n
输出描述：
数据一个整数，表示数组A中`k-优雅子数组`的数量
行尾不要有多余空格
示例1
输入：
7 3
1 2 3 1 2 3 1
输出：
1
说明：
只有子数组[1, 2, 3, 1, 2, 3, 1]是`3-优雅数组`
示例2
输入：
7 2
1 2 3 1 2 3 1
输出：
10
说明：
10个优雅子数组分别是（下标从0计数）：
长度为4：[1, 2, 3, 1](下标0~3), [2, 3, 1, 2](下标1~4), [3, 1, 2, 3](下标2~5), [1, 2, 3, 1](下标3~6)
长度为5：[1, 2, 3, 1, 2](下标0~4), [2, 3, 1, 2, 3](下标1~5), [3, 1, 2, 3, 1](下标2~6)
长度为6：[1, 2, 3, 1, 2, 3](下标0~5), [2, 3, 1, 2, 3, 1](下标1~6)
长度为7：[1, 2, 3, 1, 2, 3, 1](下标0~6)
解题思路：
这道题使用滑窗和数组比较方便：
a、滑窗的左右指针就是数组的下标，用来截取数组。
b、数组用来记录截取数组中的各个元素的个数。
当left=0，right=0，lenInts[1] = 0 +1; lenInts=[0,1,0,0,0,0,0,0]; max=1<2，不符合右滑块向右滑动，left=0,right=1，lenInts[2] = 0 +1; lenInts=[0,1,1,0,0,0,0,0];max=1<2，不符合要求
右滑块向右滑动，left=0，right=2,lenInts[3]= 0+1; lenInts=[0,1,1,1,0,0,0,0];max=1<2，不符合要求
右滑块向右滑动，left=0，right=3，lenInts[1] = 1+1; lenInts=[0,2,1,1,0,0,0,0];max=2==2，符合要求。且后面的都符合要求，len – right= 7-3 =4
左滑块向右滑动，left=1,right=3,lenInts[1] = 2-1; lenInts=[0,1,1,1,0,0,0,0];max=1<2，不符合要求。
右滑块向右滑动，left=1,right=4，lenInts[2] =1+1; lenInts=[0,1,2,1,0,0,0,0];max=2==2，符合要求。且后面的都符合要求，len – right= 7-4 = 3
左滑块向右滑动，left=2,right=4，lenInts[2] = 2-1; lenInts=[0,1,1,1,0,0,0,0];max=1<2，不符合要求。
右滑块向右滑动，left=2,right=5,lenInts[3] = 1+1; lenInts=[0,1,1,2,0,0,0,0];max=2==2，符合要求。且后面的都符合要求，len – right= 7-5 = 2
左滑块向右滑动，left=3,right=5,lenInts[3] = 2-1; lenInts=[0,1,1,1,0,0,0,0];max=1<2，不符合要求。
右滑块向右滑动，left=3,right=6，lenInts[1] = 1+1; lenInts=[0,2,1,1,0,0,0,0];max=2==2，符合要求。且后面的都符合要求，len – right= 7-6= 1
代码实现：
package com.codernav.demo.hwod.exam;
import java.util.Arrays;
import java.util.Scanner;
/**
* @title 优雅数组
* @Description 如果一个数组中出现次数最多的元素出现大于等于k次，被称为`k-优雅数组`，k也可以被称为`优雅阈值`。
* 例如，数组`[1, 2, 3, 1, 2, 3, 1]`，它是一个`3-优雅数组`，
* 因为元素`1`出现次数大于等于3次，数组`[1, 2, 3, 1, 2]`就不是一个`3-优雅数组`，
* 因为其中出现次数最多的元素时`1`和`2`，只出现了2次。
* 给定一个数组A和k，请求出A有多少子数组是`k-优雅子数组`。
* 子数组是数组中一个或多个连续元素组成的数组。。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/28
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] ints = new int[n];
for (int i = 0; i < n; i++) {
ints[i] = sc.nextInt();
}
/**
* 将数组中的数字作为index新建一个长度为A的lenInts数组（数组中元素<=n）
* lenInts数组中的数字则为index出现的次数
*/
int[] lenInts = new int[n + 1];
int res = 0;
int right = 0;
for (int i = 0; i < n; i++) { //相当于左滑块
if (i > 0) {
lenInts[ints[i - 1]]--; //i==0时数组中没有数据所以需要区别开
} else {
lenInts[ints[i]]++;
}
int max = Arrays.stream(lenInts).max().getAsInt(); //最大值为数组中元素出现的最多次数
if (max == k) {
res += n - right; //最大次数已满足则后面自然都满足
continue;
}
for (int j = right + 1; j < n; j++) { //相当于右滑块
lenInts[ints[j]]++;
max = Arrays.stream(lenInts).max().getAsInt();
if (max == k) {
res += n - j;
right = j;
break;
}
}
}
System.out.println(res);
}
}
代码实现二：Java满分代码实现
package com.codernav.demo.hwod.exam;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
/**
* @title 优雅数组
* @Description 如果一个数组中出现次数最多的元素出现大于等于k次，被称为`k-优雅数组`，k也可以被称为`优雅阈值`。
* 例如，数组`[1, 2, 3, 1, 2, 3, 1]`，它是一个`3-优雅数组`，
* 因为元素`1`出现次数大于等于3次，数组`[1, 2, 3, 1, 2]`就不是一个`3-优雅数组`，
* 因为其中出现次数最多的元素时`1`和`2`，只出现了2次。
* 给定一个数组A和k，请求出A有多少子数组是`k-优雅子数组`。
* 子数组是数组中一个或多个连续元素组成的数组。。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/28
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] input1 = sc.nextLine().split(" ");
int n = Integer.parseInt(input1[0]);
int k = Integer.parseInt(input1[1]);
String[] input2 = sc.nextLine().split(" ");
int[] num = Arrays.stream(input2).mapToInt(Integer::parseInt).toArray();
int len = num.length;
// 记录有效优雅数组个数
int count = 0;
// map存储已经滑动窗口内重复元素的个数
Map<Integer, Integer> map = new HashMap<>();
int index = -1; // 记录上一次r位置
int l = 0;
for (int r = 0; r < len; r++) {
// 寻找满足条件的右指针
map.put(num[r], map.getOrDefault(num[r], 0) + 1);
if (map.get(num[r]) == k) {
// 寻找满足条件的左指针
while (l < r) {
if (num[l] == num[r]) {
break;
}
// 左指针l移动过程中删除窗口外记录
map.put(num[l], map.get(num[l]) - 1);
l++;
}
count += (num.length - r) * (l - index);
// 记录左指针
index = l;
// 移除左指针元素
map.put(num[r], map.get(num[r]) - 1);
l++;
}
}
System.out.println(count);
}
}
相关文章
