find-the-median-of-the-uniqueness-array

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an integer array <code>nums</code>. The uniqueness array of <code>nums</code> is the sorted array that contains the number of distinct elements of all the subarrays of <code>nums</code>. In other words, it is a sorted array consisting of <code>distinct(nums[i..j])</code>, for all <code>0 &lt;= i &lt;= j &lt; nums.length</code>.

Here, <code>distinct(nums[i..j])</code> denotes the number of distinct elements in the subarray that starts at index <code>i</code> and ends at index <code>j</code>.

Return the median of the uniqueness array of <code>nums</code>.

Note that the median of an array is defined as the middle element of the array when it is sorted in non-decreasing order. If there are two choices for a median, the smaller of the two values is taken.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [1,2,3]

Output: 1

Explanation:

The uniqueness array of <code>nums</code> is <code>[distinct(nums[0..0]), distinct(nums[1..1]), distinct(nums[2..2]), distinct(nums[0..1]), distinct(nums[1..2]), distinct(nums[0..2])]</code> which is equal to <code>[1, 1, 1, 2, 2, 3]</code>. The uniqueness array has a median of 1. Therefore, the answer is 1.
</div>

Example 2:

<div class="example-block">
Input: nums = [3,4,3,4,5]

Output: 2

Explanation:

The uniqueness array of <code>nums</code> is <code>[1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3]</code>. The uniqueness array has a median of 2. Therefore, the answer is 2.
</div>

Example 3:

<div class="example-block">
Input: nums = [4,3,5,4]

Output: 2

Explanation:

The uniqueness array of <code>nums</code> is <code>[1, 1, 1, 1, 2, 2, 2, 3, 3, 3]</code>. The uniqueness array has a median of 2. Therefore, the answer is 2.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 105</code></li>
</ul>

medianOfUniquenessArray

Find the Median of the Uniqueness Array

Find K-th Smallest Pair Distance

find-k-th-smallest-pair-distance

找出第 K 小的数对距离

Total Appeal of A String

total-appeal-of-a-string

字符串的总引力

Array

Hash Table

Binary Search

Sliding Window

给你一个整数数组 <code>nums</code> 。数组 <code>nums</code> 的 唯一性数组 是一个按元素从小到大排序的数组，包含了 <code>nums</code> 的所有非空 子数组 中不同元素的个数。

换句话说，这是由所有 <code>0 &lt;= i &lt;= j &lt; nums.length</code> 的 <code>distinct(nums[i..j])</code> 组成的递增数组。

其中，<code>distinct(nums[i..j])</code> 表示从下标 <code>i</code> 到下标 <code>j</code> 的子数组中不同元素的数量。

返回 <code>nums</code> 唯一性数组 的 中位数 。

注意，数组的 中位数 定义为有序数组的中间元素。如果有两个中间元素，则取值较小的那个。

&nbsp;

示例 1：

<div class="example-block">
输入：nums = [1,2,3]

输出：1

解释：

<code>nums</code> 的唯一性数组为 <code>[distinct(nums[0..0]), distinct(nums[1..1]), distinct(nums[2..2]), distinct(nums[0..1]), distinct(nums[1..2]), distinct(nums[0..2])]</code>，即 <code>[1, 1, 1, 2, 2, 3]</code> 。唯一性数组的中位数为 1 ，因此答案是 1 。
</div>

示例 2：

<div class="example-block">
输入：nums = [3,4,3,4,5]

输出：2

解释：

<code>nums</code> 的唯一性数组为 <code>[1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3]</code> 。唯一性数组的中位数为 2 ，因此答案是 2 。
</div>

示例 3：

<div class="example-block">
输入：nums = [4,3,5,4]

输出：2

解释：

<code>nums</code> 的唯一性数组为 <code>[1, 1, 1, 1, 2, 2, 2, 3, 3, 3]</code> 。唯一性数组的中位数为 2 ，因此答案是 2 。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 105</code></li>
</ul>