▲

3

▼

🧩 Оптимальная сортировка массива перестановками с ограничением на разницу переставляемых элементов

leetcoder, изменено 28-01-2025 , 536

Задача, что мы рассмотрим сегодня - 2948. Make Lexicographically Smallest Array by Swapping Elements

📝 Описание задачи:

• Дан массив положительных чисел nums и положительное число limit.
• Разрешено менять местами элементы массива nums[i] и nums[j], если выполняется условие:
  |nums[i] - nums[j]| <= limit.
• Необходимо получить лексикографически минимальный массив, выполняя такие операции любое количество раз.

Лексикографический порядок: Массив a меньше массива b, если на первой позиции i, где они различаются, a[i] < b[i].

💡 Идея:

Будем эксплуатировать следующие замечания:

• Элементы могут менять местами только внутри определённых групп, где (после её вырезания и сортировки) выполняется условие:
  |nums[group[i+1]] - nums[group[i]]| <= limit.
• Индексная сортировка по значениям nums поможет нас найти группы, внутри которых возможны перестановки.
• Сортировка каждой из этих групп может быть эффективно выполнена с помощью дополнительного индексного массива.

🔍 Детали подхода:

1. Сортировка индексов: На первом шаге создаём массив sorted_indices, заполняя его значениями [0, 1, ..., n-1]. Затем сортируем этот массив по значениям массива nums, чтобы определить относительный порядок элементов.
2. Разделение на группы: Проходим по отсортированным индексам, объединяя их в группы, где выполняется условие:
   |nums[sorted_indices[i+1]] - nums[sorted_indices[i]]| <= limit.
3. Сортировка групп: Создаём массив sorted_groups как копию sorted_indices. Отсортируем индексы внутри каждой группы, чтобы обеспечить правильный порядок заполнения ответа.
4. Формирование ответа: Используем оба набора индексов и заполняем финальный ответ по правилу:
   answer[sorted_groups[i]] = nums[sorted_indices[i]];

📊 Асимптотика:

• Временная сложность: O(n * log(n))
  • Сортировка индексов занимает O(n * log(n)).
  • Сортировка внутри групп также занимает O(n * log(n)), если все элементы в одной группе.
• Пространственная сложность: O(n)
  • Хранение массивов sorted_indices, sorted_groups и answer требует O(n) памяти.

💻 Исходный код:

impl Solution {
    pub fn lexicographically_smallest_array(nums: Vec<i32>, limit: i32) -> Vec<i32> {
        let n = nums.len();

        // Initialize sorted_indices to track the original positions of elements.
        let mut sorted_indices: Vec<usize> = (0..n).collect();

        // Sort sorted_indices based on the values in nums.
        sorted_indices.sort_unstable_by_key(|&i| nums[i]);

        // Prepare a new array for grouping indices that can be freely swapped.
        let mut sorted_groups = sorted_indices.clone();

        // Divide the indices into groups where swaps are allowed, and sort each group.
        let mut left = 0;
        for right in 1..=n {
            if right == n || nums[sorted_indices[right]] > nums[sorted_indices[right - 1]] + limit {
                sorted_groups[left..right].sort_unstable();
                left = right;
            }
        }

        // Create the final answer array by rearranging elements based on the sorted indices.
        let mut answer = vec![0; n];
        for i in 0..n {
            answer[sorted_groups[i]] = nums[sorted_indices[i]];
        }

        answer
    }
}

Tags:  #rust #algorithms #sort