全网最全面的华为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); } }