Техника сортировки, о которой мало говорят. Тем не менее, это помогает решить некоторые важные вопросы оптимизированным способом. Для лучшего понимания необходимо знание основ.
Алгоритм сортировки на месте, помогающий свести к минимуму количество операций записи в память. Этот алгоритм не требует дополнительного места. Весь обмен происходит в виде циклов. Каждое значение либо записывается ноль раз, если оно уже находится в правильном положении, либо записывается один раз в правильное положение.
Каждый цикл состоит из размещения элемента в его отсортированном индексе, взятия элемента в этом отсортированном индексе и размещения его в его отсортированном индексе, и повторяется до тех пор, пока массив не будет отсортирован.
Его можно рассматривать как граф, где узлы соединены с ребрами. Чтобы узел A и узел B были связаны, чтобы отсортировать массив, элементы в узле A должны быть в индексе узла B при вращении.
Этот подход весьма полезен при работе с числами в заданном диапазоне и поиске дубликатов/отсутствующих и т. д.
Идея алгоритма состоит в том, чтобы поместить элементы в их правильный индекс.
Идея алгоритма.
Предположим, есть массив arr, содержащий n различных элементов. Имея элемент A, мы можем найти его индекс, подсчитав количество элементов, меньших, чем A.
- Если элемент находится в правильном положении, просто оставьте его как есть.
- В противном случае нам нужно найти правильное положение A, подсчитав количество меньших элементов. Другой элемент B заменяется и перемещается в правильное положение. Этот процесс продолжается до тех пор, пока мы не получим элемент в исходной позиции A.
Код.
Важное примечание
Циклическая сортировкаиспользуется, когда элементы в массиве находятся в диапазоне от 1 до n, где n — размер массива.
В некоторых вопросах элементы могут быть в диапазоне от 0 до n (n = размер массива), поэтому мы подойдем к вопросу соответствующим образом, но логика и идея подхода к вопросу останутся прежними. Мы по-прежнему могли бы легко применить этот алгоритм.
ПРОБЛЕМЫ
- Отсутствует номер
// T.C. - O(N*logN), S.C. - O(1) .
int missingNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
int start = 0, end = nums.size() - 1;
// going to apply Binary Search
while(start <= end) {
// avoiding overflow
int mid = start + (end - start)/2;
if(nums[mid] > mid)
end = mid - 1;
else
start = mid + 1;
}
return start;
}
Прежде чем узнать о циклической сортировке, я решил этот вопрос с помощью алгоритма Sorting + Binary Search. Но для этого потребовалась только временная сложность O (N * log N) и пространственная сложность O (1), поскольку мы не используем никакого дополнительного вспомогательного пространства.
Но чтобы оптимизировать временную сложность до O(N), мы можем использовать циклическую сортировку, поскольку у нас есть числа от 0 до N, мы можем разместить элементы по их правильному индексу.
Как только мы получим каждое число в правильном месте, мы можем просто перебрать весь массив и найти пропущенное число.
// cyclic sort , T.C. - O(N), S.C. - O(1) .
int missingNumber(vector<int>& nums) {
int i = 0;
int n = nums.size();
while(i < n) {
int correct = nums[i]; //where this element should be in sorted array
if(correct < n && correct != i) {
swap(nums[i], nums[correct]); //put current element at correct position
}
else
i++; // move to next index
}
for(int i = 0; i < n ; i++) {
if(nums[i] != i) {
return i;
}
}
return n;
}
2. Первый отсутствующий положительный результат
int firstMissingPositive(vector<int>& nums) {
sort(nums.begin(), nums.end());
int cnt = 1;
for(int i = 0; i< nums.size(); i++) {
if(nums[i] > 0 && nums[i] == cnt) {
cnt++;
}
}
return cnt;
}
Первоначально счет может быть инициализирован с 1 (наименьшее положительное число). Затем нам нужно определить, где количество не соответствует числовым значениям, потому что решение — когда оно не равно.
Это наивное решение, поскольку интуиция состоит в том, чтобы сортировать и находить, но временная сложность составляет O (N * logN). Мы также можем использовать алгоритм бинарного поиска, но это не улучшит временную сложность.
Для дальнейшей оптимизации мы будем использовать циклическую сортировку. После его применения мы можем просто проверить, какой первый элемент в массиве nums находится не на своем месте.
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
// Using Cyclic Sort Technique
for(int i = 0; i < n; ) {
// ignoring the negative & >n numbers,
// as the 1st missing number would always lie between 1 to n
if(nums[i] > 0 && nums[i] < nums.size() && nums[nums[i] - 1] != nums[i])
swap(nums[nums[i] - 1], nums[i]);
else
i++;
}
// run a loop to check which is the 1st element, not at the correct index after sorting
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
3.Найдите повторяющийся номер
Можно применить множество методов для ее решения. Я буду обсуждать лишь некоторые из них. Наивный подход состоит в том, чтобы использовать два цикла for для решения этой задачи в T.C.-O(N²). и СК-О(1).
// T.C.-O(N*logN), S.C.-O(1)
int findDuplicate(vector<int>& nums) {
vector<int> res;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size(); i++) {
if(nums[i] == nums[i + 1]) {
return nums[i];
}
}
return -1;
}
Другой подход, который должен прийти на ум, заключается в сортировке несортированного массива таким образом, чтобы все повторяющиеся элементы располагались рядом друг с другом. Затем пройдитесь по массиву, чтобы найти повторяющийся элемент, и, как только он будет найден, верните первый дубликат.
Мы также можем воспользоваться помощью хеш-карты, это уменьшит временную сложность до O(N), но пространственная сложность тоже будет O(N), что не очень хорошо. Ну, это подход, который пришел мне в голову, когда я прочитал вопрос. Хэш-карта широко используется во многих вопросах.
// T.C.-O(N), S.C.-O(N)
int findDuplicate(vector<int>& nums) {
unordered_map<int, int> mp;
for(auto i:nums) mp[i]++;
int ans;
for(auto j : mp) {
if(j.second >= 2) {
ans = j.first;
}
}
return ans;
}
Используя циклическую сортировку, мы решаем этот вопрос в T.C.-O(N) и S.C.-O(1).
int findDuplicate(vector<int>& arr){
// cyclic sort, T.C. - O(N), S.C. - O(1)
int n = arr.size();
for(int i = 0; i < n; i++) {
while(arr[i] != i + 1 && arr[arr[i] - 1] != arr[i]) {
swap(arr[i], arr[arr[i] - 1]);
}
}
for(int i = 0;i < n; i++) {
if(i + 1 != arr[i])
return arr[i];
}
return -1;
}
4. Найти все дубликаты в массиве
// cyclic sort. T.C. - O(N), S.C. - O(1)
vector<int> findDuplicates(vector<int>& nums) {
int n = nums.size();
int i = 0;
while(i < n) {
int correct = nums[i] - 1;
if (nums[i] != nums[correct]) {
swap(nums[i], nums[correct]);
}
else {
i++;
}
}
vector<int> res;
for(int i = 0;i < n; i++) {
if(nums[i] != i + 1) {
res.push_back(nums[i]);
}
}
return res;
}
Этот вопрос также можно решить с помощью различных методов. Но использование циклической сортировки дает наиболее оптимизированное решение.
5. Найти все числа, исчезнувшие в массиве
vector<int> findDisappearedNumbers(vector<int>& nums) {
int n = nums.size();
int i = 0;
// cyclic sort . T.C.- O(N), S.C.- O(1).
while(i < n) {
int correct = nums[i] - 1;
if(nums[i] != nums[correct]) {
swap(nums[i], nums[correct]);
} else {
i++;
}
}
vector<int> res;
for(int i = 0; i < n; i++) {
if(nums[i] != i + 1)
res.push_back(i + 1);
}
return res;
}
Решите и эти проблемы.
1. Поврежденная пара
2. Перемешать строку
3. Установить несоответствие
ЗАКЛЮЧЕНИЕ
Изучая циклическую сортировку несколько месяцев назад, я столкнулся со многими трудностями в ее понимании. Я просмотрел много видео и документации, чтобы понять это. Вы должны изучить как можно больше об этом самостоятельно. Я укрепил свои знания об этом через этот блог. Я надеюсь, что это поможет вам. Если в какой-то части есть ошибка, скажите, исправлю.
