4

计算左侧和右侧至少大于K个元素的元素

 1 year ago
source link: https://www.jdon.com/72319.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

计算左侧和右侧至少大于K个元素的元素

要计算左侧和右侧至少大于K个元素的元素，您可以使用以下方法：

暴力方法： 遍历数组中的每个元素，对于每个元素，分别计算其左侧和右侧大于K的元素数量。最后统计符合条件的元素数量。

def count_elements_greater_than_k(arr, K):
    n = len(arr)
    count = 0

for i in range(n):
        left_count = sum(1 for x in arr[:i] if x > K)
        right_count = sum(1 for x in arr[i+1:] if x > K)

if left_count + right_count >= K:
            count += 1

return count

优化方法： 可以通过动态规划的方式来优化，减少左侧和右侧计数的时间复杂度。

def count_elements_greater_than_k_optimized(arr, K):
    n = len(arr)
    count = 0

left_counts = [0] * n
    right_counts = [0] * n

# 计算每个元素左侧大于K的元素数量
    for i in range(1, n):
        left_counts[i] = left_counts[i-1] + (arr[i-1] > K)

# 计算每个元素右侧大于K的元素数量
    for i in range(n-2, -1, -1):
        right_counts[i] = right_counts[i+1] + (arr[i+1] > K)

# 统计符合条件的元素数量
    for i in range(n):
        if left_counts[i] + right_counts[i] >= K:
            count += 1

return count

复杂案例：
给定一个大小为n (1 <= n <= 10^5)的数组arr[]和一个正整数k，任务是计算数组中的所有索引i ( 1<= i < n) ，使得至少k i左边的元素和 i右边至少k 个元素，它们严格小于第 i 个索引处的值（即 arr）。

Input: arr = {1,3,6,5,2,1}, k = 2
Output: 2
Explanation: 用粗体标出的元素只是有效索引，arr = {2,3,6,5,2,3}

Input: arr = {2,2,2}, k = 3
Output: 0

解决方案：
这个想法是选择一些特定的数据结构来跟踪最大值。这样我们就可以检查当前索引i是否大于左侧的最大元素。我们来看看核心思想。

我们将使用最大堆数据结构并始终保持其大小为 k。对于任何索引i，我们将检查i处的当前值（即 arr）是否大于最大堆顶元素，这意味着i左侧必须至少有k 个元素小于当前值价值。如果当前值小于最大堆顶，那么我们必须删除最大堆顶并将当前元素插入堆中，因为这将帮助我们进一步减少最大值，从而在验证时帮助其他未来元素。我们将在left[]数组中跟踪此验证。

我们将从右到左执行上述相同操作，并在right[]数组中跟踪验证。

最后，我们将遍历两个数组并检查left == 1 或 true && right == 1 或 true那么这是有效的索引。因此，增加我们的count。

分步方法：

初始化两个优先级队列maxH和maxH2来跟踪k 个最大元素，并为left[]和right[]索引创建向量。 从左到右迭代数组，更新优先级队列并标记满足left[]条件的元素。 从右向左迭代数组，更新第二个优先级队列并标记满足 right [] 条件的元素。 计算两边满足条件（ left == 1 或 true && right == 1 或 true）的元素数量。 返回计数作为结果。 
include<bits/stdc++.h>
using namespace std;

int validElements(vector<int>& nums, int k) {

//初始化两个优先队列，以跟踪最大的 k 个元素
    priority_queue<int> maxH, maxH2;

int n = nums.size();
    vector<int> left(n), right(n);

// Iterate over the array from left to right
    for(int i = 0; i < n; i++){
        if(maxH.size() < k){
            maxH.push(nums[i]);
        }
        else{
            if(maxH.top() < nums[i]) left[i] = 1;
            else{
                maxH.pop();
                maxH.push(nums[i]);
            }
        }
    }

// Iterate over the array from right to left
    for(int i = n - 1; i >= 0; i--){
        if(maxH2.size() < k){
            maxH2.push(nums[i]);
        }
        else{
            if(maxH2.top() < nums[i]) right[i] = 1;
            else{
                maxH2.pop();
                maxH2.push(nums[i]);
            }
        }
    }

//计算双方最大的 k 个元素的个数
    int count = 0;
    for(int i = 0; i < n; i++) if(left[i] && right[i]) count++;

return count;
}

int main() {

// input array and k
    vector<int> nums = {2,3,6,5,2,3};
    int k = 2;

// Call the function and print the result
    cout << validElements(nums, k) << endl;
    return 0;
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK