Сообщения

Показаны сообщения с ярлыком "Сортировка"

Найти K ближайших точек к центру

У нас есть массив points , в котором хранятся координаты точек на декартовой поверхности. Найи K точек ближайшик к центру (0, 0) . (Здесь мы имеем в виду, что расстояние между точками Евклидово) Можно вернуть список ближайших точек отсортированных в любом порядке. Ответ гарантированно существует и единственнй. Пример 1: Дано: points = [[1,3],[-2,2]] , K = 1 Результат: [[-2,2]] Пояснение: Расстояние между (1, 3) и нулевой точкой = sqrt(10). Расстояние между (-2, 2) и нулевой точкой = sqrt(8). Поскольку sqrt(8) < sqrt(10), (-2, 2) - ближайшая точка. Нам нужно найти только K = 1 блиайших точек, поэтому в ответе только [[-2,2]]. Пример 2: Дано: points = [[3,3],[5,-1],[-2,4]] , K = 2 Результат: [[3,3],[-2,4]] (Ответ [[-2,4],[3,3]] тоже принимается.) Примечания: 1 <= K <= points.length <= 10000 -10000 < points[i][0] < 10000 -10000 < points[i][1] < 10000 Идея решения Идея достаточно проста: создать массив расстояний от каждой точки до нулевой; отсортировать его; ...

Благородное число (Noble integer)

Задача. Дан целочисленный массив. Найти целое число p, если оно существует, такое, что количество элементов массива, которые больше, чем p, равно (количество таких элементов) p Если число существует, вернуть 1, иначе вернуть -1. Идея решения. Поскольку речь идёт об отношениях больше-меньше между всеми элементами, то имеет смысл отсортировать исходный массив. Затем нужно просматривать каждый эелемент массива (пропуская его дубликаты) и сравнивать, сколько элементов (больше его) ещё остались до конца массива. если число оставшихся элементов равно самому (в настоящий момент рассматриваемому) элементу, то мы нашли благородное число. public class Solution { public int solve ( ArrayList < Integer > A ) { // Total runtime: O(n log n) due to sort Collections . sort ( A ); for ( int i = 0 ; i < A . size (); i ++) { // Пропускаем все дубликаты if ( i < A . size () - 1 && A . get ...

Квадраты чисел в отсортированном массиве

Задача : дан массив А целых чисел отсортированныз в неубывающем порядке. Вернуть массив, который содержит квалраты этих чисел, тоже не в возрастающем порядке. Оригинал : Given an array of integers  A  sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order. Example 1: Input: [-4,-1,0,3,10] Output: [0,1,9,16,100] Example 2: Input: [-7,-3,2,3,11] Output: [4,9,9,49,121] Note: 1 <= A.length <= 10000 -10000 <= A[i] <= 10000 A  is sorted in non-decreasing order. Источник : https://leetcode.com/problems/squares-of-a-sorted-array/submissions/ Решение : Здесь хитрость в том, что квадрат ы отрицательных чисел положительны, поэтому их нужно вставить среди квадратов положительных чисел. class Solution {     public int[] sortedSquares(int[] arr) {         // проверка на ноль        ...