배열에서 가장 가까운 번호 가져오기
마이너스 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(ECMAScript 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);재사용을 위해 자리 표시자를 지원하는 카레 기능(http://ramdajs.com/0.19.1/docs/#curry 또는 https://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 closestToFive = getClosest(_, 5);
const output = closestToFive([4, 9, 15, 6, 2]);
console.log(output);<script src="https://cdn.jsdelivr.net/npm/lodash@4.17.20/lodash.min.js"></script>작업 코드는 다음과 같습니다.
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는 다양한 방법으로 문제를 해결하는 도구를 제공하는 유연한 언어입니다.물론 모든 것은 당신의 스타일에 달려있다.코드가 더 기능적인 경우, 다음과 같이 변동을 줄이는 것이 적합하다는 것을 알 수 있습니다.
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.map(function(k) { return Math.abs(k - x) })배열을 .기본적으로 숫자의 )을 합니다.arr를 뺀 값입니다.x다음으로 가장 작은 숫자(입력 번호에 가장 가까운 숫자)를 찾습니다.Math.min.apply(Math, indexArr)배열 수 그arr[indexArr.indexOf(min)]이것이 아마도 가장 흥미로운 부분일 것이다. 숫자는 할지 요.x）그건 저희가Math.abs()차이를 찾을 수 있습니다. ★★★★★★★★★★★★★★.array.map는 입력 배열의 맵을 작성(표시)하여 인덱스를 같은 장소에 유지합니다.가장 된 배열에서 .indexArr.indexOf(min).
그걸 증명하는 쓰레기통을 만들었어요.
모든 솔루션이 지나치게 설계되어 있습니다.
이것은 다음과 같이 간단합니다.
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
정렬된 배열(선형 검색)
지금까지의 모든 답변은 배열 전체를 검색하는 데 집중되어 있습니다.어레이는 이미 정렬되어 있으며, 실제로 가장 가까운 숫자만 원하는 것을 고려하면 이것이 가장 쉬운(빠르지 않은) 솔루션일 것입니다.
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));이 알고리즘은 바이너리 트리를 사용하는 등 대폭 개선될 수 있습니다.
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
이 솔루션에서는 조건이 충족되면 반복을 중지할 수 있는 ES5 기존 수량자를 사용합니다.
의 반대인 경우, 하나의 결과에 대해 모든 요소를 반복할 필요는 없습니다.
인 "" " " " " " 가 있습니다.delta 값 사이에 .item마지막 델타와 비교됩니다.이 값이 크거나 같으면 델타 값이 있는 다른 모든 값이 실제 값보다 크기 때문에 반복이 중지됩니다.
경우,delta에 할당되어 .delta됩니다.lastDelta.
.22 「」가 됩니다.2.
값이 큰 priority가 있는 경우 델타 체크를 다음과 같이 변경해야 합니다.
if (delta >= lastDelta) {
대상:
if (delta > lastDelta) {
// ^^^ without equal sign
이 일은 와 관련이 있을 것이다22, 「」42('Priority'의 priority).
이 함수에는 배열에 정렬된 값이 필요합니다.
우선순위가 작은 코드 값:
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다른 답변에서는 어레이 전체를 반복해야 한다고 제안했습니다.
- 각 원소의 편차를 계산하다
- 가장 작은 편차와 그 요소를 추적하다
- 마지막으로 배열 전체를 반복한 후 편차가 가장 작은 요소를 반환합니다.
어레이가 이미 정렬되어 있으면 의미가 없습니다.모든 편차를 계산할 필요가 없습니다. 예를 들어, 100만 개의 요소가 정렬된 집합에서는 일치하는 항목을 찾기 위해 최대 19개의 편차를 계산하기만 하면 됩니다.이를 위해서는 바이너리 검색 방식을 사용합니다.
function findClosestIndex(arr, element) {
let from = 0, until = arr.length - 1
while (true) {
const cursor = Math.floor((from + until) / 2);
if (cursor === from) {
const diff1 = element - arr[from];
const diff2 = arr[until] - element;
return diff1 <= diff2 ? from : until;
}
const found = arr[cursor];
if (found === element) return cursor;
if (found > element) {
until = cursor;
} else if (found < element) {
from = cursor;
}
}
}
결과:
console.log(findClosestIndex([0, 1, 2, 3.5, 4.5, 5], 4));
// output: 3
console.log(findClosestIndex([0, 1, 2, 3.49, 4.5, 5], 4));
// output: 4
console.log(findClosestIndex([0, 1, 2, 3.49, 4.5, 5], 90));
// output: 5
console.log(findClosestIndex([0, 1, 2, 3.49, 4.5, 5], -1));
// output: 0
O(n) 시간의 복잡성을 줄이는 보다 간단한 방법은 어레이를 1회 반복하는 것입니다.이 방법은 정렬되지 않은 어레이를 대상으로 합니다.
다음은 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는 검색 요소에 가장 가까운 값을 저장합니다.
오래된 질문에 대답해야 할지 모르겠지만, 이 게시물은 구글 검색에서 처음 등장하기 때문에, 제 솔루션과 2c를 여기에 추가하는 것을 양해해 주셨으면 합니다.
귀찮은 나머지 이 질문에 대한 해결책이 LOUP가 될 수 있다는 것을 믿을 수 없었기 때문에 조금 더 검색하여 필터 기능을 가지고 돌아왔습니다.
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);
그게 다야!
비슷한 질문에 대한 저의 답변은 동점을 설명하는 것입니다.또한 바이너리 검색을 사용하지 않기 때문에 O(logN)가 아닌 O(N)입니다.
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(log n)의 시간 복잡성을 줄일 수 있습니다.
const myArray = [2, 42, 82, 122, 162, 202, 242, 282, 322, 362];
const binaryClosestIdx = (arr, target) => {
let start = 0;
let end = arr.length - 1;
let mid = Math.floor((start + end) / 2);
while (1) {
if (arr[mid] === target) {
return mid;
}
else if (start >= end) {
break;
}
else if (arr[mid] > target) {
end = mid - 1;
} else {
start = mid + 1;
}
mid = Math.floor((start + end) / 2);
}
// Return the closest between the last value checked and it's surrounding neighbors
const first = Math.max(mid - 1, 0);
const neighbors = arr.slice(first, mid + 2);
const best = neighbors.reduce((b, el) => Math.abs(el - target) < Math.abs(b - target) ? el : b);
return first + neighbors.indexOf(best);
}
const closestValue = myArray[binaryClosestIdx(myArray, 80)];
console.log(closestValue);구조:
대상 값을 배열의 중간 요소와 비교합니다.중간 요소가 더 크면 그 이후의 모든 요소는 무시해도 됩니다. 왜냐하면 그 요소는 더 커지기 때문입니다.중간 요소가 작을 때도 마찬가지로 그 앞에 있는 모든 요소를 무시할 수 있습니다.
타깃 값이 발견되면 반환됩니다.그렇지 않으면 가장 가까운 값은 이들 3가지 값 사이밖에 되지 않기 때문에 마지막으로 테스트한 값을 주변 네이버와 비교합니다.
또 다른 변형으로는 머리와 발끝을 연결하는 원형 레인지로 주어진 입력에 최소값만 허용됩니다.이를 통해 암호화 알고리즘 중 하나의 문자 코드 값을 얻을 수 있었습니다.
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;
});
}
가장 효율적인 것은 바이너리 검색입니다.그러나 간단한 솔루션이라도 다음 번호가 현재와 더 일치할 경우 종료될 수 있습니다.여기의 거의 모든 솔루션에서는 어레이가 주문되어 있는 것을 고려하지 않고, 모든 것을 반복하고 있습니다./
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)
바꾸다find로.findIndex배열의 인덱스를 반환합니다.
배열에서 가장 가까운 두 개의 번호를 찾으려면
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));
축소 함수를 사용하지 않고 아래 논리를 사용하여 가장 가까운 숫자를 찾을 수 있습니다.
let arr = [0, 80, 10, 60, 20, 50, 0, 100, 80, 70, 1];
const n = 2;
let closest = -1;
let closeDiff = -1;
for (let i = 0; i < arr.length; i++) {
if (Math.abs(arr[i] - n) < closeDiff || closest === -1) {
closeDiff = Math.abs(arr[i] - n);
closest = arr[i];
}
}
console.log(closest);
#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();
}
좁은 범위의 경우 가장 간단한 것은 예를 들어 80번째 엔트리에 값 82를 포함하는 맵 배열을 갖는 것입니다.훨씬 크고 희박한 범위의 경우 바이너리 검색을 사용하는 것이 좋습니다.
쿼리 언어를 사용하면 입력 번호의 양쪽에 어느 정도의 거리를 두고 값을 쿼리한 다음 축소 목록을 정렬할 수 있습니다.그러나 SQL에는 "깨끗한" 솔루션을 제공하기 위해 "다음" 또는 "이전"이라는 개념이 없습니다.
언급URL : https://stackoverflow.com/questions/8584902/get-the-closest-number-out-of-an-array
'source' 카테고리의 다른 글
| java.lang의 원인StackOverflowError(스택오버플로우오류) (0) | 2023.01.12 |
|---|---|
| Ajax POST 요청으로 인해 장고 CSRF 체크가 실패함 (0) | 2023.01.12 |
| Ubuntu에서 Oracle의 Java를 기본 Java로 설정하는 방법은 무엇입니까? (0) | 2023.01.12 |
| MySQL Update 쿼리의 '필드 목록'에 알 수 없는 열이 있습니다. (0) | 2023.01.12 |
| 도커가 PHP로 mariadb에 연결할 수 없습니다. (0) | 2023.01.02 |