limit-occurrences-in-sorted-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 a sorted integer array <code>nums</code> and an integer <code>k</code>.

Return an array such that each distinct element appears at most <code>k</code> times, while preserving the relative order of the elements in <code>nums</code>.

Note: If a distinct element appears at least <code>k</code> times, then it must appear exactly <code>k</code> times in the resulting array.

&nbsp;
Example 1:

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

Output: [1,1,2,2,3]

Explanation:

Each element can appear at most 2 times.

<ul>
	<li>The element 1 appears 3 times, so only 2 occurrences are kept.</li>
	<li>The element 2 appears 2 times, so both occurrences are kept.</li>
	<li>The element 3 appears 1 time, so it is kept.</li>
</ul>

Thus, the resulting array is <code>[1, 1, 2, 2, 3]</code>.
</div>

Example 2:

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

Output: [1,2,3]

Explanation:

All elements are distinct and already appear at most once, so the array remains unchanged.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 100</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 100</code></li>
	<li><code>nums</code> is sorted in non-decreasing order.</li>
	<li><code>1 &lt;= k &lt;= nums.length</code></li>
</ul>

&nbsp;
Follow-up:

<ul>
	<li>Can you solve this in-place using O(1) extra space?</li>
	<li>Note that the space used for returning or resizing the result does not count toward the space complexity mentioned above, as some languages do not support in-place resizing.</li>
</ul>

第 503 场周赛

weekly-contest-503

limitOccurrences

中级工程师

Limit Occurrences in Sorted Array

Array

Two Pointers

给你一个&nbsp;按升序排序&nbsp;的整数数组 <code>nums</code> 和一个整数 <code>k</code>。

返回一个数组，使得每个&nbsp;不同&nbsp;元素最多出现 <code>k</code> 次，同时保持 <code>nums</code> 中元素的相对顺序不变。

&nbsp;

示例 1：

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

输出： [1,1,2,2,3]

解释：

每个元素最多可以出现 2 次。

<ul>
	<li>元素 1 出现了 3 次，因此只保留其中 2 次。</li>
	<li>元素 2 出现了 2 次，因此全部保留。</li>
	<li>元素 3 出现了 1 次，因此保留。</li>
</ul>

因此，结果数组为 <code>[1, 1, 2, 2, 3]</code>。
</div>

示例 2：

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

输出： [1,2,3]

解释：

所有元素都互不相同，且已经最多只出现一次，因此数组保持不变。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 100</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 100</code></li>
	<li><code>nums</code> 按非递减顺序排序。</li>
	<li><code>1 &lt;= k &lt;= nums.length</code></li>
</ul>

&nbsp;

进阶：

<ul>
	<li>你能使用原地算法，并仅使用 <code>O(1)</code> 额外空间解决该问题吗？</li>
	<li>注意：用于返回结果或调整结果大小所占用的空间不计入上述空间复杂度，因为有些语言不支持原地调整数组大小。</li>
</ul>