2023年华为OD机考真题：优雅数组

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