получить ближайший номер из массива

Question

У меня есть число от минус 1000 до плюс 1000, и у меня есть массив с числами в нем.Например:

[2, 42, 82, 122, 162, 202, 242, 282, 322, 362]

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

Например, я получаю 80 как число, которое я хочу получить82.

Answer 1

Мой ответ на аналогичный вопрос также касается связей, и он написан на простом Javascript, хотя он не использует бинарный поиск, поэтому O (N), а не O (logN):

var searchArray= [0, 30, 60, 90];
var element= 33;

function findClosest(array,elem){
    var minDelta = null;
    var minIndex = null;
    for (var i = 0 ; i<array.length; i++){
        var delta = Math.abs(array[i]-elem);
        if (minDelta == null || delta < minDelta){
            minDelta = delta;
            minIndex = i;
        }
        //if it is a tie return an array of both values
        else if (delta == minDelta) {
            return [array[minIndex],array[i]];
        }//if it has already found the closest value
        else {
            return array[i-1];
        }

    }
    return array[minIndex];
}
var closest = findClosest(searchArray,element);

https://stackoverflow.com/a/26429528/986160

Answer 2

#include <algorithm>
#include <iostream>
#include <cmath>

using namespace std;

class CompareFunctor
{

public:
    CompareFunctor(int n) { _n = n; }
    bool operator()(int & val1, int & val2)
    {
        int diff1 = abs(val1 - _n);
        int diff2 = abs(val2 - _n);
        return (diff1 < diff2);
    }

private:
    int _n;
};

int Find_Closest_Value(int nums[], int size, int n)
{
    CompareFunctor cf(n);
    int cn = *min_element(nums, nums + size, cf);
    return cn;
}

int main()
{
    int nums[] = { 2, 42, 82, 122, 162, 202, 242, 282, 322, 362 };
    int size = sizeof(nums) / sizeof(int);
    int n = 80;
    int cn = Find_Closest_Value(nums, size, n);
    cout << "\nClosest value = " << cn << endl;
    cin.get();
}

Answer 3

Вот фрагмент кода, чтобы найти ближайший элемент к числу из массива в Сложности O (nlog (n)): -

Ввод: - {1,60,0, -10,100,87,56} Элемент: - 56 Ближайший номер в массиве: - 60

Исходный код (Java):

package com.algo.closestnumberinarray;
import java.util.TreeMap;


public class Find_Closest_Number_In_Array {

    public static void main(String arsg[]) {
        int array[] = { 1, 60, 0, -10, 100, 87, 69 };
        int number = 56;
        int num = getClosestNumber(array, number);
        System.out.println("Number is=" + num);
    }

    public static int getClosestNumber(int[] array, int number) {
        int diff[] = new int[array.length];

        TreeMap<Integer, Integer> keyVal = new TreeMap<Integer, Integer>();
        for (int i = 0; i < array.length; i++) {

            if (array[i] > number) {
                diff[i] = array[i] - number;
                keyVal.put(diff[i], array[i]);
            } else {
                diff[i] = number - array[i];
                keyVal.put(diff[i], array[i]);
            }

        }

        int closestKey = keyVal.firstKey();
        int closestVal = keyVal.get(closestKey);

        return closestVal;
    }
}

Answer 4

В другом варианте мы имеем круговой диапазон, соединяющий головку с носком и принимающий только минимальное значение для данного входа.Это помогло мне получить значения кодов символов для одного из алгоритмов шифрования.

function closestNumberInCircularRange(codes, charCode) {
  return codes.reduce((p_code, c_code)=>{
    if(((Math.abs(p_code-charCode) > Math.abs(c_code-charCode)) || p_code > charCode) && c_code < charCode){
      return c_code;
    }else if(p_code < charCode){
      return p_code;
    }else if(p_code > charCode && c_code > charCode){
      return Math.max.apply(Math, [p_code, c_code]);
    }
    return p_code;
  });
}

Answer 5

Для небольшого диапазона самая простая вещь - это иметь массив карт, где, например, 80-я запись будет иметь значение 82, чтобы использовать ваш пример.Для гораздо большего, разреженного диапазона, вероятно, стоит пойти бинарным поиском.

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

Answer 6

Будет работать слегка измененный двоичный поиск в массиве.