2488.统计中位数为K的子数组

链接：2488.统计中位数为K的子数组
难度：Hard
标签：数组、哈希表、前缀和
简介：给你一个长度为 n 的数组 nums ，该数组由从 1 到 n 的 不同 整数组成。另给你一个正整数 k 。统计并返回 num 中的 中位数 等于 k 的非空子数组的数目。

题解 1 - cpp

• 编辑时间：2022-11-27
• 执行用时：76ms
• 内存消耗：51.4MB
• 编程语言：cpp
• 解法介绍：因为是中位数且只有一个，找到唯一的 k，向左遍历记录情况存储，再向右遍历统计。

#define X first
#define Y second
#define lb(x) ((x) & (-x))
#define mem(a,b) memset(a,b,sizeof(a))
#define debug freopen("r.txt","r",stdin)
#define pi pair<int,int>
using namespace std;
typedef long long ll;
class Solution {
public:
    int countSubarrays(vector<int>& nums, int k) {
        int ans = 1, idx = findK(nums, k), n = nums.size();
        unordered_map<int, int> m;
        pi item = make_pair(0, 0);
        for (int i = idx - 1; i >= 0; i--) {
            if (nums[i] > k) item.Y += 1;
            else item.X += 1;
            if (item.Y - item.X == 0 || item.Y - item.X == 1) ans++;
            m[item.Y - item.X]++;
        }
        item = make_pair(0, 0);
        for (int j = idx + 1; j < n; j++) {
          if (nums[j] > k) item.Y += 1;
          else item.X += 1;
          if (item.Y - item.X == 0) ans += 1 + m[0] + m[1];
          else if (item.Y - item.X == 1) ans += 1 + m[0] + m[-1];
          else ans += m[item.X - item.Y] + m[item.X - item.Y + 1];
        }
        return ans;
    }
    int findK(vector<int>& nums, int k) {
      for (int i = 0; i < nums.size(); i++) if (nums[i] == k) return i;
      return -1;
    }
};

题解 2 - cpp

• 编辑时间：2023-03-16
• 执行用时：76ms
• 内存消耗：51.4MB
• 编程语言：cpp
• 解法介绍：遍历，对于每个值判断前面可取值，并存入map。

class Solution {
public:
    int countSubarrays(vector<int>& nums, int k) {
        unordered_map<int, int> m;
        int res = 0, cur = 0;
        bool findK = false;
        for (auto &num : nums) {
            if (num > k) cur += 1;
            else if (num < k) cur -= 1;
            if (num == k) findK = true;
            if (findK) res += m[cur] + m[cur - 1] + (cur == 0 || cur == 1);
            else m[cur]++;
        }
        return res;
    }
};

题解 3 - python

• 编辑时间：2023-03-16
• 执行用时：120ms
• 内存消耗：16.7MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        l = [set() for _ in range(n)]
        for [n1, n2] in roads:
            l[n1].add(n2)
            l[n2].add(n1)
        res = 0
        for i in range(n):
            for j in range(n):
                if i != j:
                    res = max(res, len(l[i]) + len(l[j]) + (-1 if j in l[i] else 0))
        return res

题解 4 - rust

• 编辑时间：2023-03-16
• 执行用时：16ms
• 内存消耗：3.2MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn count_subarrays(nums: Vec<i32>, k: i32) -> i32 {
        let mut m = std::collections::HashMap::<i32, i32>::new();
        let (mut res, mut cur, mut find_k) = (0, 0, false);
        for num in nums {
            if num > k {
                cur += 1;
            } else if num < k {
                cur -= 1;
            } else {
                find_k = true;
            }
            if find_k {
                res += *m.get(&cur).unwrap_or(&0)
                    + *m.get(&(cur - 1)).unwrap_or(&0)
                    + ((cur == 0 || cur == 1) as i32);
            } else {
                *m.entry(cur).or_insert(0) += 1;
            }
        }
        res
    }
}