План курса / Все задачи / Алгоритмы и структуры данных

Сумма отклонений

средне

# решено

Даны два массива целых чисел: nums1 и nums2. Для каждого элемента из nums2 найдите ближайшее по значению число в массиве nums1 и вычислите модуль разности между ними. Верните сумму всех этих разностей.

Пример 1:

Ввод: nums1 = [9,3,6,100], nums2 = [3,8,7]
Вывод: 2
Объяснение:
Для числа 3 ближайшее 3 (|3 - 3| = 0)
Для числа 8 ближайшее 9 (|8 - 9| = 1)
Для числа 7 ближайшее 6 (|7 - 6| = 1)
Ответ: 0 + 1 + 1 = 2

Пример 2:

Ввод: nums1 = [50], nums2 = [10,20,30,40]
Вывод: 100

Ограничения:

len(nums1) ≥ 1
len(nums2) ≥ 1

public class Solution {
    public static int FindMinimum(List<int> nums1, List<int> nums2) {
        // Сортируем оба массива
        nums1.Sort();
        nums2.Sort();

        int p1 = 0;
        int p2 = 0;
        int total = 0;

        // Для каждого элемента nums2 находим ближайший в nums1
        while (p2 < nums2.Count) {
            if (p1 < nums1.Count - 1 &&
                Math.Abs(nums2[p2] - nums1[p1]) > Math.Abs(nums2[p2] - nums1[p1 + 1]))
            {
                p1++;
            } else {
                // Добавляем минимальную разницу
                total += Math.Abs(nums2[p2] - nums1[p1]);
                p2++;
            }
        }
        return total;
    }
}

#include <vector>

using namespace std;

int findMinimum(vector<int> &nums1, vector<int> &nums2) {
    // Сортируем оба массива
    sort(nums1.begin(), nums1.end());
    sort(nums2.begin(), nums2.end());

    int p1 = 0;
    int p2 = 0;
    int total = 0;

    // Для каждого элемента nums2 находим ближайший в nums1
    while (p2 < nums2.size()) {
        if (p1 < nums1.size() - 1 &&
            abs(nums2[p2] - nums1[p1]) > abs(nums2[p2] - nums1[p1 + 1]))
        {
            p1++;
        } else {
            // Добавляем минимальную разницу
            total += abs(nums2[p2] - nums1[p1]);
            p2++;
        }
    }
    return total;
}

package main

import (
    "sort"
)

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func findMinimum(nums1 []int, nums2 []int) int {
    // Сортируем оба массива
    sort.Ints(nums1)
    sort.Ints(nums2)

    p1 := 0
    p2 := 0
    total := 0

    // Для каждого элемента nums2 находим ближайший в nums1
    for p2 < len(nums2) {
        if p1 < len(nums1)-1 &&
            abs(nums2[p2]-nums1[p1]) > abs(nums2[p2]-nums1[p1+1]) {
            p1++
        } else {
            // Добавляем минимальную разницу
            total += abs(nums2[p2] - nums1[p1])
            p2++
        }
    }
    return total
}

import java.util.*;

public class Solution {
    public int findMinimum(List<Integer> nums1, List<Integer> nums2) {
        // Сортируем оба массива
        Collections.sort(nums1);
        Collections.sort(nums2);

        int p1 = 0;
        int p2 = 0;
        int total = 0;

        // Для каждого элемента nums2 находим ближайший в nums1
        while (p2 < nums2.size()) {
            if (p1 < nums1.size() - 1 &&
                Math.abs(nums2.get(p2) - nums1.get(p1)) > Math.abs(nums2.get(p2) - nums1.get(p1 + 1))) {
                p1++;
            } else {
                // Добавляем минимальную разницу
                total += Math.abs(nums2.get(p2) - nums1.get(p1));
                p2++;
            }
        }
        return total;
    }
}

from typing import List

def find_minimum(nums1: List[int], nums2: List[int]) -> int:
    # Сортируем оба массива
    nums1.sort()
    nums2.sort()

    p1 = 0
    p2 = 0
    total = 0

    # Для каждого элемента nums2 находим ближайший в nums1
    while p2 < len(nums2):
        if p1 < len(nums1) - 1 and abs(nums2[p2] - nums1[p1]) > abs(nums2[p2] - nums1[p1 + 1]):
            p1 += 1
        else:
            # Добавляем минимальную разницу
            total += abs(nums2[p2] - nums1[p1])
            p2 += 1

    return total

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @returns {number}
 */
export function findMinimum(nums1, nums2) {
    // Сортируем оба массива
    nums1.sort((a, b) => a - b);
    nums2.sort((a, b) => a - b);

    let p1 = 0;
    let p2 = 0;
    let total = 0;

    // Для каждого элемента nums2 находим ближайший в nums1
    while (p2 < nums2.length) {
        if (p1 < nums1.length - 1 &&
            Math.abs(nums2[p2] - nums1[p1]) > Math.abs(nums2[p2] - nums1[p1 + 1])) {
            p1++;
        } else {
            // Добавляем минимальную разницу
            total += Math.abs(nums2[p2] - nums1[p1]);
            p2++;
        }
    }

    return total;
}

Оценка сложности

Время: O(n*log(n) + m*log(m)), где n - размер nums1, m - размер nums2
Память: O(1)

Память будет O(1) только в случае heap sort. Однако во многих языках по умолчанию используется timsort или introsort, и их потребление памяти обычно колеблется от O(log(n)) до O(n).

На собеседовании можно уточнить, что вы предполагаете использование heap sort. Для этого не нужно подключать отдельную библиотеку или писать реализацию с нуля — чаще всего достаточно просто озвучить это, чтобы показать понимание различий.