华为OD机试真题-优雅子数组（C++ Java Python）

目录

题目内容

题目解释

解题思路

题目图解

Java代码

Python代码

C++代码

题目内容

如果一个数组中出现次数最多的元素出现大于等于K次，被称为K -优雅数组，k也可以被称为优雅阈值。例如，数组[ 1，2，3，1、2，3，1 ]，它是一个3 - 优雅数组，因为元素 1 出现次数大于等于3次; 再举个例子，数组 [ 1 , 2 , 3 , 1 , 2 ] 就不是一个 3 - 优雅数组，因为其中出现次数最多的元素是1和2，只出现了2次 ( 2 小于 3，因此不满足 3 - 优雅数组的定义)。

给定一个数组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]

输入描述
第一行输入两个数字，以空格隔开，含义是: A数组长度 k值
第二行输入A数组元素，以空格隔开

输出描述
输出A有多少子数组是k-优雅子数组

输入：
7 3
1 2 3 1 2 3 1

输出：
1

题目解释

例如数组[ 1 ，2， 2， 3] ,首先看看它总共有多少个子数组：

[ 1 ]
[ 1, 2 ]
[ 1 , 2 , 2 ]
[ 1, 2 , 2 , 3 ]
[ 2 ]
[ 2 , 2 ]
[ 2 , 2 , 3]
[ 2 , 3 ]
[ 3 ]

然后，我们需要理解什么是 2 - 优雅子数组 。它表示数组中最多的重复元素次数大于等于2。 那么哪些子数组满足条件呢？

[ 1 , 2 , 2 ] ：元素 2 出现次数最多，它重复出现 2 次。因此，它是2 - 优雅子数组。

[ 1, 2 , 2 , 3 ]：元素 2 出现次数最多，它重复出现 2 次。因此，它是2 - 优雅子数组。

[ 2 , 2 ]：元素 2 出现次数最多，它重复出现 2 次。因此，它是2 - 优雅子数组。

[ 2 , 2 , 3]：元素 2 出现次数最多，它重复出现 2 次。因此，它是2 - 优雅子数组。

综上所述，在[ 1 ，2， 2， 3]的所有子数组中，总共有 4 个数组满足 2 - 优雅子数组。

解题思路

这道题使用双指针来解题。最开始的时候，两个指针left和right，都指向数组的第一个元素。然后使用哈希表numCount来记录元素出现的次数。

在right指针向右遍历的过程中，将当前元素加入哈希表并更新出现次数。

如果当前元素出现次数大于等于k，那么以left开始，以right结束的子数组都满足k-优雅子数组。

• 更新left指针的元素在numCount中的次数并向右移动left指针。再次检查，以left开始，以right结束的子数组是否满足k-优雅子数组。如果仍满足，重复本操作。

继续向右移动right指针，重复以上步骤，直到left和right指针都到达数组末尾。

题目图解

我们以 [1 , 2 , 3, 1]为例，寻找 2 - 优雅子数组。

首先，初始化 left 指针， right 指针，都指向数组的第一个元素。

此时，left 和 right 指针之间的数组为 [ 1 ], 它不满足 2 - 优雅子数组。因此，继续移动 right 指针。

此时，left 和 right 指针之间的数组为 [ 1 , 2 ], 它不满足 2 - 优雅子数组。因此，继续移动 right 指针。

此时，left 和 right 指针之间的数组为 [ 1 , 2 , 3 ], 它不满足 2 - 优雅子数组。因此，继续移动 right 指针。

此时，left 和 right 指针之间的数组为 [ 1 , 2 , 3 , 1 ], 它满足 2 - 优雅子数组。我们将统计结果 +1 。然后，移动 left指针。

最终，我们寻找到了 1个 2 - 优雅子数组 。

Java代码

import java.util.Scanner;
import java.util.HashMap;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int arrayLength = in.nextInt();
        int k = in.nextInt();
        int[] nums = new int[arrayLength];
        for (int i = 0; i < arrayLength; i++) {
            nums[i] = in.nextInt();
        }

        int elegantSubarrays = countElegantSubarrays(arrayLength, k, nums);
        System.out.println(elegantSubarrays);
    }

    public static int countElegantSubarrays(int arrayLength, int k, int[] nums) {
        int result = 0;

        int left = 0;
        int right = 0;
        HashMap<Integer, Integer> numCount = new HashMap<>();

        while (left < arrayLength && right < arrayLength) {
            Integer currentNum = nums[right];
            numCount.put(currentNum, numCount.getOrDefault(currentNum, 0) + 1);
            if (numCount.get(currentNum) >= k) {
                result += arrayLength - right;

                numCount.put(nums[left], numCount.get(nums[left]) - 1);
                left++;

                numCount.put(currentNum, numCount.get(currentNum) - 1);
                right--;
            }
            right++;
        }
        return result;
    }
}

Python代码

import sys
from collections import Counter, defaultdict

def count_kelegant_subarrays(arr_len, k_value, arr_elements):
    result = 0
    left = 0
    right = 0
    element_count = {}

    while (left < arr_len and right < arr_len):
        current_element = arr_elements[right]
        
        if (current_element in element_count):
            element_count[current_element] += 1
        else:
            element_count[current_element] = 1

        if (element_count[current_element] >= k_value):
            result += arr_len - right
            element_count[arr_elements[left]] -= 1
            left += 1
            element_count[current_element] -= 1
            right -= 1
        right += 1

    return result

input_params = [int(x) for x in input().split(" ")]
arr_len = input_params[0]
k_value = input_params[1]
arr_elements = [int(x) for x in input().split(" ")]

print(count_kelegant_subarrays(arr_len, k_value, arr_elements))

C++代码

#include<iostream>
#include<vector>
#include<string>
#include<map>
using namespace std;

vector<int> split_string_to_int(string input) {
    vector<int> nums;
    while (input.find(" ") != string::npos) {
        int found = input.find(" ");
        nums.push_back(stoi(input.substr(0, found)));
        input = input.substr(found + 1);
    }    
    nums.push_back(stoi(input));
    return nums;
}

int main()
{
    string first_line;
    getline(cin, first_line);
    vector<int> params = split_string_to_int(first_line);
    int array_length  = params[0];
    int threshold = params[1];

    string second_line;
    getline(cin, second_line);
    vector<int> numbers = split_string_to_int(second_line);

    int result = 0;

    int left = 0;
    int right = 0;
    map<int, int> num_count;

    // 使用滑动窗口遍历数组
    while (left < array_length && right < array_length) {
        int current_num = numbers[right];
        if (num_count.count(current_num)) {
            num_count[current_num] += 1;
        } else {
            num_count[current_num] = 1;
        }
        
        if (num_count[current_num] >= threshold) {
            result += array_length - right;

            num_count[numbers[left]] -= 1;
            left++;

            num_count[current_num] -= 1;

            right--;
        }
        right++;
    }

    cout << result;

    return 0;
}