Ссылка на заголовок: https://leetcode -cn.com/probl…
Сложность: простая
Название Описание
Учитывая целочисленный массив в диапазоне 1 ≤ a [i] ≤ n размера), некоторые элементы в массиве появляются дважды, другие появляются только один раз.
Найдите все числа в диапазоне [1, n], которые не отображаются в массиве.
Можете ли вы сделать это без использования дополнительной пространственной и временной сложности O (n)? Можно предположить, что возвращаемый массив не включен в дополнительное пространство.
Примеры
Input: [4,3,2,7,8,2,3,1] Output: [5,6]
размышляющий
Принцип выдвижного ящика: одна редиска, одна косточка
1.
Каждый элемент в массиве имеет свой соответствующий индекс массива (например, элемент 2, соответствующий индекс массива которого равен 1), и мы хотим получить те индексы массива, которые не совпадают с элементами
/**
*Drawer principle
* @param Integer[] $nums
* @return Integer[]
*/
function findDisappearedNumbers($nums) {
$len = count($nums);
#Match the index with the array element
#Relationship between subscript and element [element-1 = subscript]
for($i=0;$i<$len;$i++){
$index = ($nums[$i]-1)%$len;
$nums[$index] += $len;
}
$res = [];
#Grabs no matched subscripts
for($i=0;$i<$len;$i++){
if($nums[$i] <= $len){
$res[] = $i+1;
}
}
return $res;
}