the-k-strongest-values-in-an-array

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

Algorithms

Given an array of integers <code>arr</code> and an integer <code>k</code>.

A value <code>arr[i]</code> is said to be stronger than a value <code>arr[j]</code> if <code>|arr[i] - m| &gt; |arr[j] - m|</code> where <code>m</code> is the centre of the array. 
If <code>|arr[i] - m| == |arr[j] - m|</code>, then <code>arr[i]</code> is said to be stronger than <code>arr[j]</code> if <code>arr[i] &gt; arr[j]</code>.

Return a list of the strongest <code>k</code> values in the array. return the answer in any arbitrary order.

The centre is the middle value in an ordered integer list. More formally, if the length of the list is n, the centre is the element in position <code>((n - 1) / 2)</code> in the sorted list (0-indexed).

<ul>
	<li>For <code>arr = [6, -3, 7, 2, 11]</code>, <code>n = 5</code> and the centre is obtained by sorting the array <code>arr = [-3, 2, 6, 7, 11]</code> and the centre is <code>arr[m]</code> where <code>m = ((5 - 1) / 2) = 2</code>. The centre is <code>6</code>.</li>
	<li>For <code>arr = [-7, 22, 17,&thinsp;3]</code>, <code>n = 4</code> and the centre is obtained by sorting the array <code>arr = [-7, 3, 17, 22]</code> and the centre is <code>arr[m]</code> where <code>m = ((4 - 1) / 2) = 1</code>. The centre is <code>3</code>.</li>
</ul>

<div class="simple-translate-system-theme" id="simple-translate">
<div>
<div class="simple-translate-button isShow" style="background-image: url(&quot;moz-extension://8a9ffb6b-7e69-4e93-aae1-436a1448eff6/icons/512.png&quot;); height: 22px; width: 22px; top: 266px; left: 381px;">&nbsp;</div>

<div class="simple-translate-panel " style="width: 300px; height: 200px; top: 0px; left: 0px; font-size: 13px;">
<div class="simple-translate-result-wrapper" style="overflow: hidden;">
<div class="simple-translate-move" draggable="true">&nbsp;</div>

<div class="simple-translate-result-contents">
&nbsp;

&nbsp;
</div>
</div>
</div>
</div>
</div>

&nbsp;
Example 1:

<pre>
Input: arr = [1,2,3,4,5], k = 2
Output: [5,1]
Explanation: Centre is 3, the elements of the array sorted by the strongest are [5,1,4,2,3]. The strongest 2 elements are [5, 1]. [1, 5] is also accepted answer.
Please note that although |5 - 3| == |1 - 3| but 5 is stronger than 1 because 5 &gt; 1.
</pre>

Example 2:

<pre>
Input: arr = [1,1,3,5,5], k = 2
Output: [5,5]
Explanation: Centre is 3, the elements of the array sorted by the strongest are [5,5,1,1,3]. The strongest 2 elements are [5, 5].
</pre>

Example 3:

<pre>
Input: arr = [6,7,11,7,6,8], k = 5
Output: [11,8,6,6,7]
Explanation: Centre is 7, the elements of the array sorted by the strongest are [11,8,6,6,7,7].
Any permutation of [11,8,6,6,7] is accepted.
</pre>

&nbsp;
Constraints:

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