count-subarrays-with-median-k

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Consider changing the numbers that are strictly greater than k in the array to 1, the numbers that are strictly smaller than k to -1, and k to 0.

After the change, what property does a subarray with median k have in the new array?

An array with median k should have a sum equal to either 0 or 1 in the new array and should contain the element k. How do you count such subarrays?

Algorithms

You are given an array <code>nums</code> of size <code>n</code> consisting of distinct integers from <code>1</code> to <code>n</code> and a positive integer <code>k</code>.

Return the number of non-empty subarrays in <code>nums</code> that have a median equal to <code>k</code>.

Note:

<ul>
	<li>The median of an array is the middle element after sorting the array in ascending order. If the array is of even length, the median is the left middle element.

	<ul>
		<li>For example, the median of <code>[2,3,1,4]</code> is <code>2</code>, and the median of <code>[8,4,3,5,1]</code> is <code>4</code>.</li>
	</ul>
	</li>
	<li>A subarray is a contiguous part of an array.</li>
</ul>

&nbsp;
Example 1:

<pre>
Input: nums = [3,2,1,4,5], k = 4
Output: 3
Explanation: The subarrays that have a median equal to 4 are: [4], [4,5] and [1,4,5].
</pre>

Example 2:

<pre>
Input: nums = [2,3,1], k = 3
Output: 1
Explanation: [3] is the only subarray that has a median equal to 3.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i], k &lt;= n</code></li>
	<li>The integers in <code>nums</code> are distinct.</li>
</ul>

第 321 场周赛

weekly-contest-321

countSubarrays

高级专家

Count Subarrays With Median K

Number of Subarrays with Bounded Maximum

number-of-subarrays-with-bounded-maximum

区间子数组个数

Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold

大小为 K 且平均值大于等于阈值的子数组数目

Sum of Imbalance Numbers of All Subarrays

sum-of-imbalance-numbers-of-all-subarrays

所有子数组中不平衡数字之和

Array

Hash Table

Prefix Sum

给你一个长度为 <code>n</code> 的数组 <code>nums</code> ，该数组由从 <code>1</code> 到 <code>n</code> 的 不同 整数组成。另给你一个正整数 <code>k</code> 。

统计并返回 <code>nums</code> 中的 中位数 等于 <code>k</code> 的非空子数组的数目。

注意：

<ul>
	<li>数组的中位数是按 递增 顺序排列后位于 中间 的那个元素，如果数组长度为偶数，则中位数是位于中间靠 左 的那个元素。

	<ul>
		<li>例如，<code>[2,3,1,4]</code> 的中位数是 <code>2</code> ，<code>[8,4,3,5,1]</code> 的中位数是 <code>4</code> 。</li>
	</ul>
	</li>
	<li>子数组是数组中的一个连续部分。</li>
</ul>

&nbsp;

示例 1：

<pre>
输入：nums = [3,2,1,4,5], k = 4
输出：3
解释：中位数等于 4 的子数组有：[4]、[4,5] 和 [1,4,5] 。
</pre>

示例 2：

<pre>
输入：nums = [2,3,1], k = 3
输出：1
解释：[3] 是唯一一个中位数等于 3 的子数组。
</pre>

&nbsp;

提示：

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i], k &lt;= n</code></li>
	<li><code>nums</code> 中的整数互不相同</li>
</ul>

统计中位数为 K 的子数组

执行通过

错误解答

超出内存限制

超出输出限制

超出时间限制

执行出错

内部出错

编译出错

超时

Restrictions Failed

给你一个长度为 n 的数组 nums ，该数组由从 1 到 n 的 不同 整数组成。另给你一个正整数 k 。

统计并返回 nums 中的 中位数 等于 k 的非空子数组的数目。

注意：

 * 数组的中位数是按 递增 顺序排列后位于 中间 的那个元素，如果数组长度为偶数，则中位数是位于中间靠 左 的那个元素。
 * 例如，[2,3,1,4] 的中位数是 2 ，[8,4,3,5,1] 的中位数是 4 。
 * 子数组是数组中的一个连续部分。

 

示例 1：


输入：nums = [3,2,1,4,5], k = 4
输出：3
解释：中位数等于 4 的子数组有：[4]、[4,5] 和 [1,4,5] 。


示例 2：


输入：nums = [2,3,1], k = 3
输出：1
解释：[3] 是唯一一个中位数等于 3 的子数组。


 

提示：

 * n == nums.length
 * 1 <= n <= 105
 * 1 <= nums[i], k <= n
 * nums 中的整数互不相同