Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
AlexZZZ79
2 / 2 / 0
Регистрация: 02.09.2014
Сообщений: 81
1

Найти мин.разницу по модулю между двумя любыми элементами двух массивов

14.03.2018, 11:16. Просмотров 259. Ответов 10
Метки нет (Все метки)

Есть массив А и B.Нужно найти мин.разницу по модулю между двумя любыми элементами массива.
Те min(abs(a[i]-b[j]).
Решение должно быть быстрее ,чем просто перебор.Есть идеи?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.03.2018, 11:16
Ответы с готовыми решениями:

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

Найти и напечатать наибольшую разницу по модулю между двумя соседними числами
Дано натуральное число N, за ним последовательность из N действительных чисел. Найти и напечатать...

Найти сумму чисел, которые находятся между Мин. и Макс по модулю элементами массива
Есть такая вот задача: Найти сумму чисел, которые находятся между Мин. и Макс по модулю элементами...

Процедура: найти разницу между максимальным положительным и минимальным элементами массивов
Что сделать что бы в этой строчки "if c>max then max:=c;" ,а по-идеи и в той где min, не выдавало...

Определить максимальную разницу между двумя соседними элементами массива
Помогите пожалуйста. Хотя бы частью программы Задание: Напишите программу, которая позволяет...

10
grgdvo
799 / 658 / 237
Регистрация: 02.09.2012
Сообщений: 1,942
14.03.2018, 14:48 2
отсортировать оба массива по возрастанию, двигаться одновременно двумя индексами i и j по двум массивам, проверять abs(a[i]-b[j]). индексы i и j двигать на основании сравнения a[i] < ? > b[j]. минимальной будет та разница, где элементы близки друг к другу, соответственно, надо двигать индекс меньшего значения ближе к большему.
Если ничего не напутал, то будет [2 * O(n log n) + O(2n)], что быстрее, чем полный перебор [O(n^2)]
1
AlexZZZ79
2 / 2 / 0
Регистрация: 02.09.2014
Сообщений: 81
14.03.2018, 17:09  [ТС] 3
Так я и сделал.Но я думал может что есть за O(N).

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// Finding min difference between item and any els in array
    private static int binarySearchDiff(int[] array, int item) {
        Arrays.sort(array);// N*LogN
        int left = 0;
        int right = array.length - 1;
        if (item <= array[0]) {
            return Math.abs(item - array[0]);
        }
        if (item >= array[right]) {
            return Math.abs(item - array[right]);
        }
 
        while (left <= right) {
            int mid = (left + right) / 2; // get middle
            if (item == array[mid] || item == array[left] || item == array[right]) {
                return 0;
            }
 
            if (item > array[left] && item < array[right] && right == left + 1) {
 
                int diff1 = item - array[left];
                int diff2 = array[right] - item;
                return Math.min(diff1, diff2);
            }
 
            if (item <= array[mid])
                right = mid;
            else
                left = mid;
        }
        return 0;
 
    }
 
    public static int getMinAbsDiff(int[] array1, int[] array2) {
 
        int min = Integer.MAX_VALUE;
 
        for (int i = 0; i < array2.length; i++) {
 
            int diff = binarySearchDiff(array1, array2[i]);
            if (diff == 0)
                return 0;
 
            if (min >= diff) {
                min = diff;
            }
 
        }
 
        return min;
 
    }
0
grgdvo
799 / 658 / 237
Регистрация: 02.09.2012
Сообщений: 1,942
14.03.2018, 23:34 4
Код не соответствует. Вы пробегаете по каждому элементу array2. Для каждого этого элемента вы сортируете array1 и в нем пытаетесь методом бинарного поиска (половинного деления) найти элемент с минимальной разницей.
Здесь как минимум O(n * (n log n + log n)), то есть еще хуже чем полный перебор.
0
AlexZZZ79
2 / 2 / 0
Регистрация: 02.09.2014
Сообщений: 81
15.03.2018, 23:20  [ТС] 5
Я согласен.Нужно отсортировать один раз.Это и подразумевалось.
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// Finding min difference between item and any els in array
    private static int binarySearchDiff(int[] array, int item) {
        
        int left = 0;
        int right = array.length - 1;
        if (item <= array[0]) {
            return Math.abs(item - array[0]);
        }
        if (item >= array[right]) {
            return Math.abs(item - array[right]);
        }
 
        while (left <= right) {
            int mid = (left + right) / 2; // get middle
            if (item == array[mid] || item == array[left] || item == array[right]) {
                return 0;
            }
 
            if (item > array[left] && item < array[right] && right == left + 1) {
 
                int diff1 = item - array[left];
                int diff2 = array[right] - item;
                return Math.min(diff1, diff2);
            }
 
            if (item <= array[mid])
                right = mid;
            else
                left = mid;
        }
        return 0;
 
    }
 
    public static int getMinAbsDiff(int[] array1, int[] array2) {
 
        int min = Integer.MAX_VALUE;
        Arrays.sort(array1);// N*LogN
        for (int i = 0; i < array2.length; i++) {
 
            int diff = binarySearchDiff(array1, array2[i]);
            if (diff == 0)
                return 0;
 
            if (min >= diff) {
                min = diff;
            }
 
        }
 
        return min;
 
    }
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,494
16.03.2018, 00:32 6
Цитата Сообщение от AlexZZZ79 Посмотреть сообщение
Это и подразумевалось.
Подразумевалось отсортировать оба массива и в процессе (фиктивного) слияния запомнить минимальную разницу между элементами.
0
AlexZZZ79
2 / 2 / 0
Регистрация: 02.09.2014
Сообщений: 81
16.03.2018, 09:18  [ТС] 7
Не вижу причину для спора.Мое последнее решение вполне работоспособное.Сложность N*log N.Памяти не требует дополнительной,кроме локальных переменных.Если решение неверное,то прошу поправить.
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,494
16.03.2018, 11:53 8
Фактически, Вы сортируете второй массив, для каждого элемента определяя методом бинарного поиска место, куда его поставить. Не думаю, что это хороший способ сортировать массив.

Можно обойтись без функции бинарного поиска. Примерно так:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static int getMinAbsDiff(int[] array1, int[] array2)
{
    int min = int.MaxValue;
    Array.Sort(array1);// N*LogN
    Array.Sort(array2);// N*LogN
    int i = 0, j = 0;
    while(true)
    {
        int d = array2[j] - array1[i];
        if(d > 0)
        {
            if(d < min)
                min = d;
            if(++i >= array1.Length)
                return min;
            continue;
        }
        if(d < 0)
        {
            if(-d < min)
                min = -d;
            if(++j >= array2.Length)
                return min;
            continue;
        }
        return 0;
    }
}
(код не проверял - возможны опечатки)
1
AlexZZZ79
2 / 2 / 0
Регистрация: 02.09.2014
Сообщений: 81
16.03.2018, 12:23  [ТС] 9
Ок.По сложности алгоритма мои код и ваш сопоставимы.По сути алгоритма - ваш проще понять.Но мне в голову он сразу не пришел-)Пришло в голову - модифицировать бинарный поиск.Спасибо возьму на вооружение.
0
salam
187 / 168 / 29
Регистрация: 10.07.2012
Сообщений: 782
17.03.2018, 21:03 10
разве не правда, что ответ всегда достигается на паре (мин/макс первого массива, мин/макс второго) ?
0
AlexZZZ79
2 / 2 / 0
Регистрация: 02.09.2014
Сообщений: 81
17.03.2018, 21:09  [ТС] 11
Нет.Минимальная разница это 0.Те когда элементы совпадают по значению.То есть определенно мин/макс здесь не помогут.
10,3,1 и 5,3,2 =>0 мин.разница.
0
17.03.2018, 21:09
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.03.2018, 21:09

Найти расстояние между двумя любыми точками
Клеточное поле образовано вертикальными и горизонтальными прямыми так, что первая прямая находится...

Найти соотношение между максимальными элементами двух массивов
Помогите с подготовкой к экзамену, пожалуйста. Тут задание: найти соотношение между максимальными...

В одномерном массиве. Найти произведение элементов, расположенных между макс по модулю и мин по модулю значениямми
Здравствуйте, помогите пожалуйста, не получается написать программку. В одномерном массиве из N...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru