minimum-removals-to-balance-array

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given an integer array <code>nums</code> and an integer <code>k</code>.

An array is considered balanced if the value of its maximum element is at most <code>k</code> times the minimum element.

You may remove any number of elements from <code>nums</code>​​​​​​​ without making it empty.

Return the minimum number of elements to remove so that the remaining array is balanced.

Note: An array of size 1 is considered balanced as its maximum and minimum are equal, and the condition always holds true.

&nbsp;
Example 1:

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

Output: 1

Explanation:

<ul>
	<li>Remove <code>nums[2] = 5</code> to get <code>nums = [2, 1]</code>.</li>
	<li>Now <code>max = 2</code>, <code>min = 1</code> and <code>max &lt;= min * k</code> as <code>2 &lt;= 1 * 2</code>. Thus, the answer is 1.</li>
</ul>
</div>

Example 2:

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

Output: 2

Explanation:

<ul>
	<li>Remove <code>nums[0] = 1</code> and <code>nums[3] = 9</code> to get <code>nums = [6, 2]</code>.</li>
	<li>Now <code>max = 6</code>, <code>min = 2</code> and <code>max &lt;= min * k</code> as <code>6 &lt;= 2 * 3</code>. Thus, the answer is 2.</li>
</ul>
</div>

Example 3:

<div class="example-block">
Input: nums = [4,6], k = 2

Output: 0

Explanation:

<ul>
	<li>Since <code>nums</code> is already balanced as <code>6 &lt;= 4 * 2</code>, no elements need to be removed.</li>
</ul>
</div>

&nbsp;
Constraints:

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

第 162 场双周赛

biweekly-contest-162

minRemoval

高级工程师

Minimum Removals to Balance Array

Array

Binary Search

Sorting

Sliding Window

给你一个整数数组 <code>nums</code> 和一个整数 <code>k</code>。

如果一个数组的&nbsp;最大&nbsp;元素的值&nbsp;至多&nbsp;是其&nbsp;最小&nbsp;元素的 <code>k</code> 倍，则该数组被称为是&nbsp;平衡&nbsp;的。

你可以从 <code>nums</code> 中移除&nbsp;任意&nbsp;数量的元素，但不能使其变为&nbsp;空&nbsp;数组。

返回为了使剩余数组平衡，需要移除的元素的&nbsp;最小&nbsp;数量。

注意：大小为 1 的数组被认为是平衡的，因为其最大值和最小值相等，且条件总是成立。

&nbsp;

示例 1:

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

输出：1

解释：

<ul>
	<li>移除 <code>nums[2] = 5</code> 得到 <code>nums = [2, 1]</code>。</li>
	<li>现在 <code>max = 2</code>, <code>min = 1</code>，且 <code>max &lt;= min * k</code>，因为 <code>2 &lt;= 1 * 2</code>。因此，答案是 1。</li>
</ul>
</div>

示例 2:

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

输出：2

解释：

<ul>
	<li>移除 <code>nums[0] = 1</code> 和 <code>nums[3] = 9</code> 得到 <code>nums = [6, 2]</code>。</li>
	<li>现在 <code>max = 6</code>, <code>min = 2</code>，且 <code>max &lt;= min * k</code>，因为 <code>6 &lt;= 2 * 3</code>。因此，答案是 2。</li>
</ul>
</div>

示例 3:

<div class="example-block">
输入：nums = [4,6], k = 2

输出：0

解释：

<ul>
	<li>由于 <code>nums</code> 已经平衡，因为 <code>6 &lt;= 4 * 2</code>，所以不需要移除任何元素。</li>
</ul>
</div>

&nbsp;

提示：

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