Найти ближайшее число в данном массиве

21

Это вдохновлено реальной проблемой, с которой я столкнулся. Мне любопытно посмотреть, есть ли какой-нибудь умный способ пойти по этому поводу.

Вам даны два несортированных массива, A и B, каждый из которых содержит произвольное число с плавающей точкой. A и B не обязательно имеют одинаковую длину. Напишите функцию, которая последовательно принимает элементы A и находит ближайшее значение в массиве B. Результат должен содержаться в новом массиве.

Условие выигрыша

Самый короткий код выигрывает (как обычно).

Orhym
источник
1
Округлить до ближайшего целого числа?
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
1
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Я читаю это как «округлить каждый элемент A до ближайшего элемента B»
Джон Дворак
@JanDvorak: Хорошо, я понимаю часть о направлении округления, но проблема не указала, сколько цифр.
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Округлить до ближайшего числа. Ответ должен выводить числа с плавающей точкой из массива / списка B.
Orhym
1
Будут ли отсортированы массивы A и B?
Уровень Река St

Ответы:

17

APL, 13 17

(21 байт в UTF-8)

B[{↑⍋|⍵-B}¨A]

Если вы хотите истинную лямбду (A как левый аргумент и B как правый):

{⍵[⍺{↑⍋|⍺-⍵}¨⊂⍵]}

Как это работает:

{...}¨Aвызывает лямбда-функцию {...}с каждым значением A (вместо вызова с A в качестве массива), собирая результаты в массив одинаковой формы

|⍵-B вычисляет абсолютные значения разности между аргументом ⍵ и всем в B (- вычитание, | - абс).

↑⍋ принимает индекс наименьшего элемента (array сортирует массив, возвращая индексы, ↑ получает первый элемент)

B[...] просто выбирает элемент (ы) по индексу (ам).

Решение довольно простое, хотя оно использует замечательную особенность функции сортировки APL, возвращающей вектор перестановки (индексы отсортированного элемента в исходном массиве), а не сам отсортированный массив.

Vovanium
источник
Как это работает?
Джон Дворак
Объяснил в ответе
Вованиум
Откуда ты знаешь, как это написать?
Мартейн
Это как писать по-китайски. Для меня нет большой разницы, когда я пишу чужие слова или чужие символы ...
Вованиум
17

Математика - 17

#&@@@Nearest@A/@B

Как это работает? Да, я признаю, что здесь есть немного обмана, потому что Mathematica имеет встроенную ближайшую функциональность. Все остальное просто и связано с размещением результата в одномерном массиве. Это выглядит некрасиво только из-за дополнительных усилий, чтобы сделать его коротким.

Сабольч
источник
1
Ха! Добро пожаловать! :)
Доктор Велизарий
6

C # - 103 97 87 байт

Я не совсем уверен, правильно ли я понял этот вопрос, но в любом случае вот мое решение. Я использовал списки вместо массивов, потому что это позволяет мне писать более короткий код.

Целочисленный массив короче целочисленного списка.

Входные данные:

t(new int[] { 0, 25, 10, 38 }, new int[] { 3, 22, 15, 49, 2 });

Метод:

void t(int[]a,int[]b){var e=a.Select(c=>b.OrderBy(i=>Math.Abs(c-i)).First()).ToArray();

Выход:

2, 22, 15, 49

Если мой ответ неверный, оставьте комментарий под ним.

РЕДАКТИРОВАТЬ: Как @grax указал, теперь вопрос о плавает. Поэтому я бы тоже хотел включить его ответ.

95 байт (ответ Гракс)

float[]t(float[]a,float[]b){return a.Select(d=>b.OrderBy(e=>Math.Abs(e-d)).First()).ToArray();}
tsavinho
источник
Списки тоже хорошо.
Орхим
1
Переименуйте itemв iи вы сохраните 6 дополнительных символов;)
Ашратт
@ Aschratt большое спасибо!
Цавиньо
3
1. Функция специально не говорит о возвращении нового значения, но я думаю, что вы должны. 2. Так как вопрос вызвал float, я думаю, что вы должны использовать floatfloat[] t(float[] a, float[] b) {return a.Select(d=>b.OrderBy(e=>Math.Abs(e-d)).First()).ToArray();}
Grax32
@Grax Когда я написал свой первый ответ, вопрос был не о поплавках. Поскольку вопрос был обновлен, я включил и ваш ответ. Большое спасибо.
tsavinho
5

R, 41 символ

B[apply(abs(outer(A,B,`-`)),1,which.min)]

Объяснение:

outer(A,B,`-`)вычисляет для каждого элемента x разности A x-Bи выводит результат в виде матрицы (размерной длины (A) x длины (B)).
which.minвыбирает индекс минимального числа.
apply(x, 1, f)применяет функцию fк каждой строке матрицы x.
Так apply(abs(outer(A,B,`-`)),1,which.min)возвращает индексы минимальной абсолютной разности между каждым элементом A и элементами вектора B.

Использование:

> A <- runif(10,0,50)
> B <- runif(10,0,50)
> A
[1] 10.0394987 23.4564467 19.6667152 36.7101256 47.4567670 49.8315028  2.1321263 19.2866901  0.7668489 22.5539178
> B
[1] 44.010174 32.743469  1.908891 48.222695 16.966245 23.092239 24.762485 30.793543 48.703640  6.935354
> B[apply(abs(outer(A,B,`-`)),1,which.min)]
[1]  6.935354 23.092239 16.966245 32.743469 48.222695 48.703640  1.908891 16.966245  1.908891 23.092239
plannapus
источник
5

CJam - 14

q~
f{{1$-z}$0=\;}
p

Основной код находится на второй строке, остальное для использования стандартного ввода и красивого вывода.

Попробуйте это на http://cjam.aditsu.net/

Объяснение:

q~считывает и оценивает входные данные
f{...}выполняет блок для каждого элемента первого массива и следующего объекта (который является вторым массивом), собирая результаты в массив
{...}$сортирует второй массив с использованием блока для вычисления ключа для каждого элемента
1$копирует текущий элемент из первого массива
-zвычитает, затем принимает абсолютное значение,
0=принимает первое значение отсортированного массива (значение с минимальным ключом)
\;отбрасывает элемент из первого массива,
pпечатает строковое представление результата

Примеры (вдохновленные другими ответами):

Вход: [10.1 11.2 12.3 13.4 9.5] [10 12 14]
Выход:[10 12 12 14 10]

Вход: [0 25 10 38] [3 22 15 49 2]
Выход:[2 22 15 49]

aditsu
источник
4

Javascript (E6) 54 56 59

Минимизируйте расстояние. Используя квадрат вместо пресса, просто сохраните символы.
Редактировать алгебру ...
Редактировать исправление бесполезного назначения (остаток теста без определения функции)

F=(A,B)=>A.map(a=>B.sort((x,y)=>x*x-y*y+2*a*(y-x))[0])

Было F=(A,B)=>D=A.map(a=>B.sort((x,y)=>((x-=a,y-=a,x*x-y*y))[0])

Тестовое задание

F([10.1, 11.2, 12.3, 13.4, 9.5],[10, 12, 14])

Результат: [10, 12, 12, 14, 10]

edc65
источник
1
D=не требуется, так как mapвозвращает новый массив. Альтернативная (той же длины) функция сортировки:(x,y)=>(x-=a)*x-(y-=a)*y
nderscore
4

Python 3.x - 55 символов

f=lambda a,b:[min((abs(x-n),x)for x in b)[1]for n in a]

aи bявляются входными массивами, а требуемый массив является результатом выражения.

Tal
источник
Я отредактировал ответ, чтобы сделать его функцией, поскольку вопрос требует функции.
user80551
3

Хаскелл, 55

c a b=[[y|y<-b,(y-x)^2==minimum[(z-x)^2|z<-b]]!!0|x<-a]

Сначала я подумал об использовании minimumByи comparing, но поскольку их нет в Prelude, потребовалось множество символов, чтобы их квалифицировать. Также украли идею возведения в квадрат из некоторых других ответов, чтобы сбрить персонажа.

YawarRaza7349
источник
3

PowerShell - 44

$a|%{$n=$_;($b|sort{[math]::abs($n-$_)})[0]}

пример

С $aи $bустановите:

$a = @(36.3, 9, 50, 12, 18.7, 30)
$b = @(30, 10, 40.5, 20)

Выход

40.5, 10, 40.5, 10, 20, 30
Rynant
источник
Вы можете использовать float в примере, чтобы было ясно, что он также обрабатывает float
bebe
@bebe - Спасибо, обновил, чтобы было понятно.
Rynant
-3 байта:$a|%{$n=$_;($b|sort{($n-$_)*($n-$_)})[0]}
mazzy
2

Руби, 40

f=->a,b{a.map{|x|b.min_by{|y|(x-y)**2}}}

То же, что и в ответе на Python, но возведение в квадрат немного сложнее, чем любой другой способ получить абсолютное значение.

histocrat
источник
2

Pyth - 12 11 байт

Примечание: Pyth намного моложе, чем этот вызов, поэтому этот ответ не имеет права на победу.

Простой метод, использует oфункцию заказа, чтобы получить минимальное расстояние и mустановить его над списком a.

mho.a-dNQvz

m    vz    Map over evaled first input and implicitly print
 ho Q      Minimal mapped over evaled second input
  .a-      Absolute difference
   d       Lambda param 1
   b       Lambda param 2

Попробуйте это онлайн здесь .

Maltysen
источник
@ Якуб, о, да, прости.
Maltysen
2

TI-BASIC, 24

∟A+seq(min(∟B+i²∟A(N)),N,1,dim(∟A

Не приближается к APL, но использует менее мощные функции - здесь не используются функции «отсортировано по» или «индекс наименьшего». Недостатком TI-BASIC здесь является отсутствие этих функций и многомерных массивов.

Ungolfed:

seq(       ,N,1,dim(∟A           #Sequence depending on the Nth element of list A
    ∟A(N)+min(   +0i)            #Number with minimum absolute value, add to ∟A(N)
              ∟B-∟A(N)           #Subtracts Nth element of ∟A from all elements of B

Функция min (имеет два поведения: при использовании с действительными числами или списками она дает наименьшее значение; однако при использовании с комплексными числами или списками она дает значение с наименьшим абсолютным значением. Добавление 0iили умножение на i^2заставляет интерпретатор используйте второе поведение, поэтому min(1,-2)возвращает, -2тогда как min(1+0i,-2+0i)возвращает 1.

lirtosiast
источник
1

Фортран 90: 88

function f();integer::f(size(a));f(:)=[(b(minloc(abs(a(i)-b))),i=1,size(a))];endfunction

Это требует, чтобы это было containотредактировано в пределах полной программы:

program main
   real :: a(5), b(3)
   integer :: i(size(a))
   a = [10.1, 11.2, 12.3, 13.4, 9.5]
   b = [10, 12, 14]
   i = f()
   print*,i
 contains
   function f()
     integer :: f(size(a))
     f(:)=[(b(minloc(abs(a(i)-b))),i=1,size(a))]
   end function
end program main

Квадратные скобки объявляют массив, в то время как (...,i=)представляет подразумеваемый doцикл; Затем я возвращаю значение, bдля которого элемент a(i)-bсвернут.

Кайл Канос
источник
1

Матлаб: 48

f=@(a)B(abs(B-a)==min(abs(B-a)));C=arrayfun(f,A)

Предполагается, что Aи Bявляются одномерными матрицами в рабочей области. Окончательный результат находится Cв рабочей области. Это, вероятно, также будет работать в Октаве. Условное индексирование делает это довольно тривиальным.

Годрик Провидец
источник
0

С 144 163

#define f float
f T, *C, m;
f *q(f *A, f *B, int S, f s)
{
    if(m) 
        return abs(T - *A) - abs(T - *B);
    for ( 
        C = malloc(S * 4);
        m = S--;
        C[S] = *B
    ) 
        T = A[S], 
        qsort(B, s, 4, q);
    return C;
}

Хорошо ... Я думаю, что этот маленький код нуждается в объяснении.

Сначала я попытался выполнить работу с двумя уровнями цикла for, чтобы найти минимальную разницу, и установил текущее значение как минимум значения B. Это очень просто.

То же самое можно сделать с помощью функции qsort и функции сравнения. Я делаю это сортировать B по разнице вместо элементов B. Слишком много функций для такого маленького алгоритма. Таким образом, функция q теперь служит двум целям. Во-первых, это сам алгоритм, во-вторых (когда его вызывает qsort) компаратор. Для связи между двумя государствами я должен был объявить глобальные.

m обозначает, находится ли он в состоянии компаратора или в основном .

пример:

float A[] = {1.5, 5.6, 8.9, -33.1};
float B[] = {-20.1, 2.2, 10.3};
float *C;

C = q(A, B, sizeof(A)/sizeof(*A), sizeof(B)/sizeof(*B));
// C holds 2.2,2.2,10.3,-20.1
Бебе
источник
Считает ли 166/163 пробел или нет?
Кайл Канос
Конечно нет. Пробелы и новые строки предназначены для простоты понимания.
bebe
0

GolfScript, 49 байт

Примечание: это частичное решение. Я работаю над тем, чтобы сделать это комплексное решение

{{\.@\.[.,,\]zip@{[\~@-abs]}+%{~\;}$0=0==}%\;}:f;

Да. GolfScript поддерживает плавающую точку. Попробуйте это здесь . Пример:

# B is [-20.1 2.2 10.3]
[-201 10 -1?*
22 10 -1?*
103 10 -1?*]

# A. No floating point numbers allowed here.
# This is because 1.5{}+ (where the 1.5 is a
# single floating point number, not 1.5,
# which would be 1 1 5) results in the block
# {1.5 }, which leads to 1 1 5 when executed
[1 5 9 -30]

Выход:

[2.2 2.2 10.3 -20.1]
Джастин
источник
0

C # 262

Программа находит минимальные различия и сохраняет наиболее близкие значения от массива B. Я скоро поработаю над игрой в гольф.

List<float> F(List<float> a, List<float> b)
{
List<float> c = new List<float>();
float diff,min;
int k;
for(int i=0; i<a.Count;i++)
{
diff=0;
min=1e6F;
k = 0;
for(int j=0; j<b.Count;j++)
{
diff = Math.Abs(a[i] - b[j]);
if (diff < min)
{
min = diff;
k = j;
}
}
c.Add(b[k]);
}
return c;
}

Полная программа с тестовым кодом

using System;
using System.Collections.Generic;
public class JGolf
{
    static List<float> NearestValues(List<float> a, List<float> b)
    {
        List<float> c = new List<float>();
        float diff,min;
        int k;
        for(int i=0; i<a.Count;i++)
        {
            diff=0;
            min=1e6F;
            k = 0;
            for(int j=0; j<b.Count;j++)
            {
                diff = Math.Abs(a[i] - b[j]);
                if (diff < min)
                {
                    min = diff;
                    k = j;
                }
            }
            c.Add(b[k]);
        }
        return c;
    }

    public static void Main(string[] args)
    {
        List<float> A = RandF(8413);
        Console.WriteLine("A");
        Print(A);
        List<float> B = RandF(9448);
        Console.WriteLine("B");
        Print(B);

        List<float> d = JGolf.NearestValues(A, B);
        Console.WriteLine("d");
        Print(d);
        Console.ReadLine();
    }

    private static List<float> RandF(int seed)
    {
        Random r = new Random(seed);
        int n = r.Next(9) + 1;
        List<float> c = new List<float>();
        while (n-- > 0)
        {
            c.Add((float)r.NextDouble() * 100);
        }
        return c;
    }

    private static void Print(List<float> d)
    {
        foreach(float f in d)
        {
            Console.Write(f.ToString()+", ");
        }
    }
}
bacchusbeale
источник
0

C #: 120

Линк потрясающий:

float[] t(float[] A, float[] B){return A.Select(a => B.First(b => Math.Abs(b-a) == B.Min(c=>Math.Abs(c-a)))).ToArray();}
DLeh
источник