배열에서 가장 가까운 숫자를 얻습니다
마이너스 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);재사용 성을 위해 플레이스 홀더를 지원하는 카레 기능 ( 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 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는 여러 가지 방법으로 문제를 해결할 수있는 도구를 제공하는 유연한 언어입니다. 물론 그것은 모두 당신의 스타일에 달려 있습니다. 코드가 더 기능적이라면 축소 변형이 적합하다는 것을 알게 될 것입니다 .
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정렬 할 수 있습니다 . 인덱스를 신경 쓰거나 미리 정렬 할 필요는 없습니다.
명확성을 위해 코드를 한 줄씩 설명하겠습니다.
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).
그것을 보여주는 쓰레기통을 만들었 습니다.
정렬 된 배열 (선형 검색)
지금까지 모든 답변은 전체 배열을 검색하는 데 집중했습니다. 배열이 이미 정렬되어 있고 가장 가까운 숫자 만 원한다는 것을 고려할 때 아마도 가장 빠른 해결책 일 것입니다.
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));이진 트리를 사용하여 알고리즘을 크게 개선 할 수 있습니다.
이 솔루션은 조건이 충족되는 경우 반복을 중지 할 수있는 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모든 솔루션이 과도하게 설계되었습니다.
다음과 같이 간단합니다.
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);
});
// 5
이전 질문에 대답해야하는지 모르겠지만이 게시물이 Google 검색에 처음 표시되므로 내 솔루션 및 2c를 여기에 추가하는 것을 용서해 주셨으면합니다.
게으 르기 때문에이 질문에 대한 해결책이 LOOP 일 것이라고 믿을 수 없었으므로 조금 더 검색하고 필터 기능으로 돌아 왔습니다 .
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 (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()했고 다른 기능보다 약간 빠르다.
배열에서 약간 수정 된 이진 검색이 작동합니다.
작은 범위의 경우 가장 간단한 방법은 맵 배열을 사용하는 것입니다. 예를 들어 80 번째 항목에 82 값이 있으면 예제를 사용할 수 있습니다. 훨씬 더 큰 희소 범위의 경우 아마도 이진 검색 일 것입니다.
쿼리 언어를 사용하면 입력 번호의 어느 정도 거리를두고 값을 쿼리 한 다음 축소 목록을 정렬 할 수 있습니다. 그러나 SQL에는 "다음"또는 "이전"이라는 개념이 없어서 "깨끗한"솔루션을 제공 할 수 있습니다.
여기서 또 다른 변형은 머리와 발끝을 연결하는 원형 범위를 가지며 주어진 입력에 최소값 만 허용합니다. 이것은 암호화 알고리즘 중 하나에 대한 char 코드 값을 얻는 데 도움이되었습니다.
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();
}
Complexity O (nlog (n))의 배열에서 숫자에 가장 가까운 요소를 찾는 코드 스 니펫은 다음과 같습니다.
입력 :-{1,60,0, -10,100,87,56} 요소 :-56 배열에서 가장 가까운 수 :-60
소스 코드 (자바) :
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;
}
}
참고 URL : https://stackoverflow.com/questions/8584902/get-closest-number-out-of-array
'IT' 카테고리의 다른 글
| 각도 컴포넌트와 모듈의 차이점 (0) | 2020.06.23 |
|---|---|
| Objective-C 2.0에서 메소드를 더 이상 사용되지 않는 것으로 플래그 지정하려면 어떻게합니까? (0) | 2020.06.23 |
| 매개 변수로서 Objective-C 패스 블록 (0) | 2020.06.23 |
| onConfigurationChanged가 호출되지 않음 (0) | 2020.06.23 |
| 테스트 어댑터가 설치된 테스트 탐색기에 NUnit 장치 테스트가 표시되지 않음 (0) | 2020.06.23 |