计算左侧和右侧至少大于K个元素的元素
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.
计算左侧和右侧至少大于K个元素的元素
要计算左侧和右侧至少大于K个元素的元素,您可以使用以下方法:
暴力方法: 遍历数组中的每个元素,对于每个元素,分别计算其左侧和右侧大于K的元素数量。最后统计符合条件的元素数量。
def count_elements_greater_than_k(arr, K): |
优化方法: 可以通过动态规划的方式来优化,减少左侧和右侧计数的时间复杂度。
def count_elements_greater_than_k_optimized(arr, K): |
复杂案例:
给定一个大小为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。
分步方法:
include<bits/stdc++.h> |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK