获取数组中最接近的数字

2020/10/23 14:24 · javascript ·  · 0评论

我有一个从负1000到正1000的数字,并且我有一个带有数字的数组。像这样:

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

我希望我得到的数字更改为数组中最接近的数字。

例如,我得到80我想要的数字82

ES5版本:

var counts = [4, 9, 15, 6, 2],
  goal = 5;

var closest = counts.reduce(function(prev, curr) {
  return (Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev);
});

console.log(closest);

这是应该可转换为任何程序语言的伪代码:

array = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]
number = 112
print closest (number, array)

def closest (num, arr):
    curr = arr[0]
    foreach val in arr:
        if abs (num - val) < abs (num - curr):
            curr = val
    return curr

它只是计算出给定数字与每个数组元素之间的绝对差,并以最小的差返回给您之一。

对于示例值:

number = 112  112  112  112  112  112  112  112  112  112
array  =   2   42   82  122  162  202  242  282  322  362
diff   = 110   70   30   10   50   90  130  170  210  250
                         |
                         +-- one with minimal absolute difference.

作为概念验证,这是我用来演示实际操作的Python代码:

def closest (num, arr):
    curr = arr[0]
    for index in range (len (arr)):
        if abs (num - arr[index]) < abs (num - curr):
            curr = arr[index]
    return curr

array = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]
number = 112
print closest (number, array)

而且,如果您真的需要Javascript,请参阅以下完整的HTML文件,该文件演示了实际的功能:

<html>
    <head></head>
    <body>
        <script language="javascript">
            function closest (num, arr) {
                var curr = arr[0];
                var diff = Math.abs (num - curr);
                for (var val = 0; val < arr.length; val++) {
                    var newdiff = Math.abs (num - arr[val]);
                    if (newdiff < diff) {
                        diff = newdiff;
                        curr = arr[val];
                    }
                }
                return curr;
            }
            array = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];
            number = 112;
            alert (closest (number, array));
        </script>
    </body>
</html>

现在请记住,例如,如果您的数据项已排序(可以从样本数据中推断出,但您未明确声明),则可能存在提高效率的余地。例如,您可以使用二进制搜索来找到最接近的项目。

你也应该记住,除非你需要做很多次每秒,效率改进将主要容易被忽视的,除非你的数据集得到很多大。

如果您确实想尝试这种方式(并且可以确保数组以升序排序),那么这是一个很好的起点:

<html>
    <head></head>
    <body>
        <script language="javascript">
            function closest (num, arr) {
                var mid;
                var lo = 0;
                var hi = arr.length - 1;
                while (hi - lo > 1) {
                    mid = Math.floor ((lo + hi) / 2);
                    if (arr[mid] < num) {
                        lo = mid;
                    } else {
                        hi = mid;
                    }
                }
                if (num - arr[lo] <= arr[hi] - num) {
                    return arr[lo];
                }
                return arr[hi];
            }
            array = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];
            number = 112;
            alert (closest (number, array));
        </script>
    </body>
</html>

它基本上使用括号和中间值检查来将每次迭代的求解空间减少一半,这是一种经典O(log N)算法,而上面的顺序搜索是O(N)

0  1  2   3   4   5   6   7   8   9  <- indexes
2 42 82 122 162 202 242 282 322 362  <- values
L             M                   H  L=0, H=9, M=4, 162 higher, H<-M
L     M       H                      L=0, H=4, M=2, 82 lower/equal, L<-M
      L   M   H                      L=2, H=4, M=3, 122 higher, H<-M
      L   H                          L=2, H=3, difference of 1 so exit
          ^
          |
          H (122-112=10) is closer than L (112-82=30) so choose H

如前所述,这对于小型数据集或不需要盲目快速的事物没有太大的区别,但这是您可能要考虑的一种选择。

ES6(2015)版本:

const counts = [4, 9, 15, 6, 2];
const goal = 5;

const output = counts.reduce((prev, curr) => Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev);

console.log(output);

为了实现可重用性,您可以包装一个支持占位符的curry函数(http://ramdajs.com/0.19.1/docs/#curryhttps://lodash.com/docs#curry)。根据您的需求,这提供了很大的灵活性:

const getClosest = curry((counts, goal) => {
  return counts
    .reduce((prev, curr) => Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev);
});

const closestTo5 = getClosest(_, 5);
const closestTo = getClosest([4, 9, 15, 6, 2]);

工作代码如下:

var array = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];

function closest(array, num) {
  var i = 0;
  var minDiff = 1000;
  var ans;
  for (i in array) {
    var m = Math.abs(num - array[i]);
    if (m < minDiff) {
      minDiff = m;
      ans = array[i];
    }
  }
  return ans;
}
console.log(closest(array, 88));

适用于未排序的数组

尽管这里发布了一些好的解决方案,但是JavaScript是一种灵活的语言,为我们提供了以多种不同方式解决问题的工具。当然,这全都取决于您的风格。如果您的代码更具功能性,那么您会发现reduce变体是合适的,即:

  arr.reduce(function (prev, curr) {
    return (Math.abs(curr - goal) < Math.abs(prev - goal) ? curr : prev);
  });

但是,根据他们的编码风格,有些人可能会觉得很难阅读。因此,我提出了一种解决问题的新方法:

  var findClosest = function (x, arr) {
    var indexArr = arr.map(function(k) { return Math.abs(k - x) })
    var min = Math.min.apply(Math, indexArr)
    return arr[indexArr.indexOf(min)]
  }

  findClosest(80, [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]) // Outputs 82

其他使用最小值的方法相反Math.min.apply这种方法不需要对输入数组arr进行排序我们不需要关心索引或事先对其进行排序。

为了清楚起见,我将逐行解释代码:

  1. arr.map(function(k) { return Math.abs(k - x) })创建一个新数组,本质上存储给定数字(中的数字arr)减去输入数字(x的绝对值接下来,我们将寻找最小的数字(也是最接近输入数字的数字)
  2. Math.min.apply(Math, indexArr) 这是在我们刚刚创建的数组中查找最小数字的合法方法(仅此而已)
  3. arr[indexArr.indexOf(min)]这也许是最有趣的部分。我们找到了最小的数字,但是不确定是否应加上或减去初始数字(x)。那是因为我们曾经Math.abs()发现差异。但是,array.map创建(逻辑上)输入数组的映射,将索引保持在同一位置。因此,要找出最接近的数字,我们只需返回给定array中找到的最小值的索引indexArr.indexOf(min)

我创建了一个演示

对于排序的数组(线性搜索)

到目前为止,所有答案都集中在搜索整个数组上。考虑到您的数组已经排序,您实际上只想要最接近的数字,这可能是最快的解决方案:

var a = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];
var target = 90000;

/**
 * Returns the closest number from a sorted array.
 **/
function closest(arr, target) {
  if (!(arr) || arr.length == 0)
    return null;
  if (arr.length == 1)
    return arr[0];

  for (var i = 1; i < arr.length; i++) {
    // As soon as a number bigger than target is found, return the previous or current
    // number depending on which has smaller difference to the target.
    if (arr[i] > target) {
      var p = arr[i - 1];
      var c = arr[i]
      return Math.abs(p - target) < Math.abs(c - target) ? p : c;
    }
  }
  // No number in array is bigger so return the last.
  return arr[arr.length - 1];
}

// Trying it out
console.log(closest(a, target));

注意,该算法可以大大改进,例如使用二叉树。

所有解决方案都经过精心设计。

它很简单:

const needle = 5;
const haystack = [1, 2, 3, 4, 5, 6, 7, 8, 9];

haystack.sort((a, b) => {
  return Math.abs(a - needle) - Math.abs(b - needle);
})[0];

// 5

此解决方案使用ES5存在量词 Array#some,如果满足条件,它可以停止迭代。

与相对Array#reduce,它不需要为一个结果迭代所有元素。

在回调内部,将delta获取搜索值和实际值之间的绝对值item,并将其与最后一个增量进行比较。如果大于或等于,则迭代会停止,因为所有其他值及其增量都大于实际值。

如果delta回调中的较小,则将实际项目分配给结果并将delta保存在中lastDelta

最后,采用具有相同增量的较小值,如以下示例中的22,结果为2

如果优先级较高,则必须将增量检查从以下位置更改:

if (delta >= lastDelta) {

至:

if (delta > lastDelta) {
//       ^^^ without equal sign

22结果将得到42(优先级更高的值)。

此函数需要数组中的排序值。


优先级较小的代码:

function closestValue(array, value) {
    var result,
        lastDelta;

    array.some(function (item) {
        var delta = Math.abs(value - item);
        if (delta >= lastDelta) {
            return true;
        }
        result = item;
        lastDelta = delta;
    });
    return result;
}

var data = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];

console.log(21, closestValue(data, 21)); // 2
console.log(22, closestValue(data, 22)); // 2  smaller value
console.log(23, closestValue(data, 23)); // 42
console.log(80, closestValue(data, 80)); // 82

优先级更高的代码:

function closestValue(array, value) {
    var result,
        lastDelta;

    array.some(function (item) {
        var delta = Math.abs(value - item);
        if (delta > lastDelta) {
            return true;
        }
        result = item;
        lastDelta = delta;
    });
    return result;
}

var data = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];

console.log(21, closestValue(data, 21)); //  2
console.log(22, closestValue(data, 22)); // 42 greater value
console.log(23, closestValue(data, 23)); // 42
console.log(80, closestValue(data, 80)); // 82

ES6

适用于排序和未排序的数组

数字整数和浮点数,欢迎使用字符串

/**
 * Finds the nearest value in an array of numbers.
 * Example: nearestValue(array, 42)
 * 
 * @param {Array<number>} arr
 * @param {number} val the ideal value for which the nearest or equal should be found
 */
const nearestValue = (arr, val) => arr.reduce((p, n) => (Math.abs(p) > Math.abs(n - val) ? n - val : p), Infinity) + val

例子:

let values = [1,2,3,4,5]
console.log(nearestValue(values, 10)) // --> 5
console.log(nearestValue(values, 0)) // --> 1
console.log(nearestValue(values, 2.5)) // --> 2

values = [100,5,90,56]
console.log(nearestValue(values, 42)) // --> 56

values = ['100','5','90','56']
console.log(nearestValue(values, 42)) // --> 56

我不知道我是否应该回答一个老问题,但是由于这篇文章首先出现在Google搜索中,所以我希望您能原谅我在此处添加我的解决方案和我的2c。

懒惰,我不敢相信这个问题的解决方案会是LOOP,所以我搜索了更多内容并返回了filter函数

var myArray = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];
var myValue = 80;

function BiggerThan(inArray) {
  return inArray > myValue;
}

var arrBiggerElements = myArray.filter(BiggerThan);
var nextElement = Math.min.apply(null, arrBiggerElements);
alert(nextElement);

就这样 !

我对类似问题的答案也考虑到了联系,并且使用纯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

我喜欢Fusion的方法,但是其中有一个小错误。这样,它是正确的:

    function closest(array, number) {
        var num = 0;
        for (var i = array.length - 1; i >= 0; i--) {
            if(Math.abs(number - array[i]) < Math.abs(number - array[num])){
                num = i;
            }
        }
        return array[num];
    }

它也更快一点,因为它使用了改进的for循环。

最后,我编写了这样的函数:

    var getClosest = function(number, array) {
        var current = array[0];
        var difference = Math.abs(number - current);
        var index = array.length;
        while (index--) {
            var newDifference = Math.abs(number - array[index]);
            if (newDifference < difference) {
                difference = newDifference;
                current = array[index];
            }
        }
        return current;
    };

我用console.time()测试过,它比其他功能要快一些。

O(n)时间复杂度的一种更简单的方法是在数组的一次迭代中执行此操作。此方法适用于未排序的数组。

以下是一个JavaScript示例,从数组中可以找到最接近“ 58”的数字。

var inputArr = [150, 5, 200, 50, 30];
var search = 58;
var min = Math.min();
var result = 0;
for(i=0;i<inputArr.length;i++) {
  let absVal = Math.abs(search - inputArr[i])
  if(min > absVal) {
    min=absVal;
    result = inputArr[i];
  }
}
console.log(result); //expected output 50 if input is 58

这将为积极工作负数十进制数。

Math.min()会回来的Infinity

result会的数据存储到最接近的搜索元素。

对该数组进行稍微修改的二进制搜索即可。

对于较小的范围,最简单的方法是拥有一个映射数组,例如,在第80个条目中的值为82,以使用您的示例。对于更大,更稀疏的范围,可能的方法是二进制搜索。

使用查询语言,您可以查询输入数字两边一定距离的值,然后对生成的简化列表进行排序。但是SQL没有“下一个”或“上一个”的良好概念,无法为您提供“干净”的解决方案。

这里的另一个变体是圆形范围,从头到脚,只接受给定输入的最小值。这帮助我获得了一种加密算法的字符码值。

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;
  });
}
#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();
}

最有效的方法是二进制搜索。但是,当下一个数字与当前数字进一步匹配即使是简单的解决方案也可能退出这里几乎所有的解决方案都没有考虑到数组是有序的,并且要遍历整个数组:/

const closest = (orderedArray, value, valueGetter = item => item) =>
  orderedArray.find((item, i) =>
    i === orderedArray.length - 1 ||
    Math.abs(value - valueGetter(item)) < Math.abs(value - valueGetter(orderedArray[i + 1])));

var data = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];

console.log('21 -> 2', closest(data, 21) === 2);
console.log('22 -> 42', closest(data, 22) === 42); // equidistant between 2 and 42, select highest
console.log('23 -> 42', closest(data, 23) === 42);
console.log('80 -> 82', closest(data, 80) === 82);

这也可以在非原语上运行,例如 closest(data, 21, item => item.age)

更改findfindIndex以返回数组中的索引。

在数组中查找两个最近的数字

function findTwoClosest(givenList, goal) {
  var first;
  var second;
  var finalCollection = [givenList[0], givenList[1]];
  givenList.forEach((item, firtIndex) => {
    first = item;

    for (let i = firtIndex + 1; i < givenList.length; i++) {
      second = givenList[i];

      if (first + second < goal) {
        if (first + second > finalCollection[0] + finalCollection[1]) {
          finalCollection = [first, second];
        }
      }
    }
  });

  return finalCollection;
}

var counts = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362]
var goal = 80;
console.log(findTwoClosest(counts, goal));

这是代码片段,用于从复杂度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;
    }
}
本文地址:http://javascript.askforanswer.com/huoqushuzuzhongzuijiejindeshuzi.html
文章标签: ,  
版权声明:本文为原创文章,版权归 javascript 所有,欢迎分享本文,转载请保留出处!

文件下载

老薛主机终身7折优惠码boke112

上一篇:
下一篇:

评论已关闭!