Алгоритмы и структуры данных: продвинутый уровень Квадраты чисел в отсортированном массиве
Выпуск 3. Квадраты чисел в отсортированном массиве
Здравствуйте, !
Задача: дан массив А целых чисел отсортированных в неубывающем
порядке. Вернуть массив, который содержит квадраты этих чисел, тоже в отсортированном порядке.
Пример 1:
Дано: [-4,-1,0,3,10]Результат: [0,1,9,16,100]
Пример 2:
Дано: [-7,-3,2,3,11]Результат: [4,9,9,49,121]
Примечания:
1 <= A.length <= 10000
-10000 <= A[i] <= 10000
Решение:
Здесь хитрость в том, что квадраты отрицательных чисел положительны,
поэтому их нужно вставить среди квадратов положительных чисел.
Можно было бы подсчитать все квадраты в том порядке, в котором они идут, а потом отсортировать со скоростью O(N*logN), где N - это длина массива А. Но мы попробуем сделать это за O(N). Для этого найдем точку, в котором отрицательные числа сменяются нулем, а потом и положительными числами. И от этой точки сделаем два указателя. Один будет идти к началу массива, а второй-к концу. И постоянно будем сравнивать, какое из двух чисел будет давать наименьший квадрат и, следовательно, должно быть рассмаотренг раньше.
class Solution {
public int[] sortedSquares(int[] arr) {
// проверка на ноль
if (arr==null) return null;
if (arr.length==0) return arr;
// результат будет того же размера, что и исходный массив
int[] result = new int[arr.length];
// ставим указатель на текущую ячейку результата (массив квадратов) // будем заполнять результирующий массив квадратами с 0 и до конца
int currindex=0;
// найдём индекс в исходном массиве, где меняется знак чисел
// changingIndex - индекс последнего отрицательного числа перед 0 или положительным
int changingIndex = findIndex(arr, 0, arr.length-1);
// если знак не менялся
if (changingIndex==-1) {
boolean isPositive = false;
if (arr[0]>=0) isPositive=true; // все неотрицат. числа в исходнике
if (isPositive) { // просто считаем квадраты
for (int i = 0; i<arr.length; i++) {
result[currindex++]=arr[i]*arr[i];
}
} else { // все только отрицательыне числа
// считаем квадраты, начиная с последнего
for (int i = arr.length-1; i>=0; i--) {
result[currindex++]=arr[i]*arr[i];
}
} // возвращаем результат, тут больше делать нечего
return result;
}
// знак менялся (changingIndex!=-1)
// если в исходнике есть 0, найдём индекс самого первого
while (changingIndex>0 && arr[changingIndex]==0) { changingIndex--;}
// от первого нуля выходят два указателя:
// один идёт влево по отрицательным числам до ячейки 0 массива
// второй - вправо по неотриц. числам до хвоста массива
int goleft = changingIndex;
int goright = changingIndex+1;
// слева ничего не осталось, "добиваем" элементы справа
if (goleft<0&&goright<arr.length) {
for (int i = goright; i < arr.length; i++) {
result[currindex++]=arr[i]*arr[i];
}
}
// справа ничего не осталось, "добиваем" элементы слева
if (goright>=arr.length && goleft>=0) {
for (int i = goleft; i>=0; i--) {
result[currindex++]=arr[i]*arr[i];
}
}
return result;
}
Осталось пояснить, как мы ищем "переломный" элемент, в котором отрицательные числа сменяются 0 или положительными числами.
Можно, конечно, тупо просканировать массив с первого элемента. Если первый (то есть нулевой) 0 или положительный, то квадраты элементов будут находиться в том же порядке. Если головной элемент отрицательный, то нужно найти первый неотрицательный элемент линейным сканированием. Это потребует O(N) операций.
А можно ещё больше ускорить итоговый алгоитм. и поискать "переломный" элемент при помощи дихотомии, или двоичным поиском.
Общая идея дихотомии: имеем некий (отсортированный) массив на рассмотрении. Берем его значение в индексе посередине. Если оно меньше требуемого результата, то нам нужно повторить поиск для правой части подмассива (где элементы больше среднего элемента). Иначе повторить для левой части подмассива (где элементы меньше среднего элемента).
Наш искомый индекс массива таков, что результат умножения двух соседних элементов дают 0 или отрицательное число.
// вспомогательная процедура, которая бинарным поиском находит
// индекс наибольшего отрицательного числа,
// т.е. которое непосредственно перед нулём.
// Если нет перехода от отрицательных к 0/неотрицательным, то возвращает -1 public int findIndex(int[] arr, int start, int end) {
while (start<end) {
int mid = (start + end)/2; // рискованная операция, но о ней в другой раз
if (mid+1<arr.length) { // есть ли пара для умножения?
int num = arr[mid]*arr[mid+1]; // если произведение двух соседних чисел отрицательно, то в исходнике нет нулей, // и мы попали в пару -+
if (num<=0) { // число * 0, причем 0 в индексе mid, а другое число тоже может быть 0
if (num==0 && arr[mid]==0) return mid; // число * 0, причем 0 в индексе mid+1
if (num==0 && arr[mid+1]==0) return mid+1; // а вот и пара -+
if (num<0 && arr[mid]<0) return mid;
}
// либо оба отрицательные, либо оба положительные
if (num>0 && arr[mid]>=0) { // если оба положительные, то правая граница поиска сдвигается влево на mid
end = mid;
} else { // если оба отрицательные, то левая граница поиска сдвигается влево на mid +1
start=mid+1;
} // конец проверки положительного произведения
} // конец проверки, есть ли пара для умножения
} // конец while, ничего не нашли, возвращаем -1
return -1;
}
}
Сложность дихотомии в отсортированном массиве составляет O(logN).
В коментариях к выпуску задайте свои вопросы, если они у вас возникли.
С уважением, Наталия Македа natalia.macheda at gmail.com 2021-03-04, Trento
Внимание! Письмо, которое вы мне отправите с вопросами и коментариями по тематике данной рассылки, может быть опубликовано полностью или частично в данной рассылке, если в нём нет явного запрета на это.
