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

Bertha 。 2024-03-22 18:53 125阅读 0赞

**目录**

题目内容

题目解释

解题思路

题目图解

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`**指针，都指向数组的**第一个元素**。  
![在这里插入图片描述][406947444a924f4c8b3debb4255760ab.png]

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

![在这里插入图片描述][189babf2f18c44eba21e586698b5015a.png]

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

![在这里插入图片描述][d9a6c25244d64707ae0504bf61ce885a.png]

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

![在这里插入图片描述][30d18d2373b847bcacc5f4f83c0ebfe8.png]

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

![在这里插入图片描述][c1f048687971452d923dae286f11cd90.png]

![在这里插入图片描述][29f0330e33fd40d78fe0c371941c48c2.png]  
![在这里插入图片描述][6a993d09bd00443caa3fe8d3837f2127.png]

最终，我们寻找到了 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;
    }

[406947444a924f4c8b3debb4255760ab.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/c853202f53ea42dba17355e43f3fc488.png
[189babf2f18c44eba21e586698b5015a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/5f964884ed5443f9ad25a78a838948d5.png
[d9a6c25244d64707ae0504bf61ce885a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/3f2e3eccaad24c88b229375faa715401.png
[30d18d2373b847bcacc5f4f83c0ebfe8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/571156019a5b40aab65319daf47c631b.png
[c1f048687971452d923dae286f11cd90.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/6c4903e875884f7fa82046e55dd3843e.png
[29f0330e33fd40d78fe0c371941c48c2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/2880240d279c4382997cf974ead26be7.png
[6a993d09bd00443caa3fe8d3837f2127.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/f78aca183d69404a82ac1938ed46913c.png