나는 가장 작은 것을 원하지 않고 두 번째로 작은 것을 원합니다
특정 오픈 소스 온라인 학습 플랫폼의 등급 시스템에 대한 나의 고투에서 영감을 얻었습니다.
제한된 내장 기능 세트가있는 컴퓨터 언어로 작업하고 있습니다. 당신은 세트가 있습니다$m$ 실수 $x_1, x_2, \dots x_m$. 이 숫자는 임의적이고 알 수없는 순서로되어 있습니다 (즉, 반드시 단조롭게 증가하거나 감소하지 않음).
중복 항목이 구별되는 것으로 취급되는이 숫자 중 "두 번째로 작은"숫자를 반환하는 함수를 작성하려고합니다. 즉, 가장 작은 숫자부터 가장 큰 숫자까지 나열하면이 함수는 순서가 지정된 목록에서 두 번째 숫자를 반환합니다. 예를 들어, 숫자가$\{ 2, 6, 1, 7\}$, 함수는 $2$. 숫자가$\{ 4, 5, 4, 4, 4, 5 \}$, 함수는 $4$.
사용할 수있는 기능은 다음과 같습니다.
max(x1, x2, ...)및min(x1, x2, ...): 임의의 수의 실수 인수를 허용합니다. 가장 큰 것 또는 가장 작은 것을 각각 반환합니다.sum(x1, x2, ...): 임의의 수의 실수 인수를 허용합니다. 모두의 합계를 반환합니다.
또한, 표준 산술 연산을 사용할 수있다 +, -, *, /,와 ^.
보너스 질문 :
방법을 확장하여 $n$세트 중 가장 작은 수.
두 질문에 대한 나의 의도 된 답변만을 사용 max, sum및 산술 연산. 그러나이 목록에 있는 다른 내장 함수를 사용하는보다 우아한 대답을 생각해 낼 수 있다면 저에게도 흥미로울 것입니다. :-)
답변
내가 올 수있는 최선의 방법은 다음과 같습니다.
$$min((x_1+x_2),(x_1+x_3),\cdots,(x_{m-1}+x_m)) - min(x_1,x_2,\cdots,x_m)$$
즉
두 숫자의 최소 합계를 찾은 다음 가장 작은 숫자로 빼십시오.
그래서 $n$-최소 :
최소 합계를 찾으십시오. $n$ 숫자의 최소 합으로 빼십시오. $n-1$ 번호.
아마도 나는 그것을 얻지 못할 수도 있지만 (내 말은, 그것은 해결책이며, 그것이 허용되는지는 모르겠습니다),하지만 :
$max(min(set_1)min(set_2)…min(set_m))$ 어디 각각 $set_k$ 모든 숫자를 포함합니다. $x_k$ (그리고 세트의 수는 $(m)$ )
그리고 $3$세 번째로 작은 숫자는 비슷합니다.
각 "세트"는 2 개를 제외한 모든 숫자와 그 조합을 모두 포함하므로 세트의 수는 다음과 같습니다. $(m)$엑스$(m-1)/2$.
그리고 $4$가장 작은 숫자는 비슷할 것입니다.
각 "세트"는 3 개를 제외한 모든 숫자와 그 조합을 모두 포함하므로 세트 수는 다음과 같습니다. $(m)$엑스$(m-1)$엑스$(m-2)/(3!)$.
3으로 나눈다! 특정 조합을 하나만 사용하기 때문에$x_i$, $x_j$, $x_k$, 무시 ($x_j$, $x_i$, $x_k$), ($x_k$, $x_i$, $x_j$), ($x_j$, $x_k$, $x_i$), ($x_k$, $x_j$, $x_i$), ($x_i$, $x_k$, $x_j$).
등등
이 솔루션은 원래 athin의 솔루션 에서 영감을 얻었 지만 가장 작은 두 숫자의 합을 생성하는 개선 된 방법이 있습니다. 이제 주석에서 제안한대로 합계를 최대 값으로 변경할 수 있고 마지막에 가장 작은 숫자를 뺄 필요가 없기 때문에 Bass 솔루션의 변형입니다 .
입력을 다음과 같이 인덱싱합시다. $x_0, x_1, \dots, x_{m-1}$. 숫자를 써라$0, 1, \dots, m-1$바이너리로. 각각$k=1,2,\dots,\lceil\log_2 m\rceil$, 허락하다 $A_k$ 모두의 분이 $x_i$ 그런 $i$ 있다 $0$ 에 $k$-번째 위치; 허락하다$B_k$ 모두의 분이 $x_i$ 그런 $i$ 있다 $1$ 에 $k$-번째 위치. 그렇다면 우리의 해결책은$$\min(\max(A_1,B_1),\max(A_2,B_2),\dots,\max(A_k,B_k)).$$ 개수 $x$이 표현에서의는 $m \lceil \log_2 m \rceil$.
이것이 작동하는 이유는 다음과 같습니다.
마다 $\max(A_k,B_k)$두 요소의 최대 값이므로 최소한 두 번째로 작은 요소입니다. 반면에$x_i$ 과 $x_j$ 가장 작은 두 가지는 $x$의, 그러면 어떤 위치가 있어야합니다 $k$ 여기서 이진 표현은 $i$ 과 $j$다르다; 말하다,$i$ 있다 $0$ 에 $k$-번째 위치 및 $j$ 있다 $1$. 그럼 우리는 얻을거야$A_k = x_i$ 과 $B_k = x_j$, 그래서 $\max(A_k,B_k) = \max(x_i,x_j)$우리가 취하는 분에 확실히 나타날 것입니다. 기타 없음$\max(A_{k'}, B_{k'})$ 더 작을 수 있으므로 $\max(x_i,x_j)$두 번째로 작은 요소 인는 최종 답입니다.
다음은 완성 된 공식의 예입니다. $m=8$:
$$\min\Big(\max(\min(x_0,x_2,x_4,x_6),\min(x_1,x_3,x_5,x_7)), \max(\min(x_0,x_1,x_4,x_5),\min(x_2,x_3,x_6,x_7)), \max(\min(x_0,x_1,x_2,x_3),\min(x_4,x_5,x_6,x_7))\Big).$$
그리고 다음은 humn이 그린 솔루션의 다이어그램입니다 .
우리는 이것을 일반화 할 수 있습니다. $O(m \log m)$ 찾기위한 솔루션 $k^{\text{th}}$1 년 전에 영리하고 잘 생긴 개인이 작성한 Math.SE 답변 에 의존하여 가장 작은 요소 입니다.
이것은 단지 임의의 구성이기 때문에 "일종"이라고 말합니다. 일부 무작위 입력에서만 작동한다는 의미는 아닙니다. 방법에서 임의성을 갖는 공식을 생성하는 방법을 설명 할 것이라는 의미에서 무작위 적입니다. 양의 확률로 모든 입력에 대해 항상 작동하는 공식을 제공합니다.
방법은 다음과 같습니다.
공식의 "절"은 다음과 같습니다. 우리는 갈라졌다$\{1,2,\dots,m\}$ 으로 $k$ 세트 $S_1, S_2, \dots, S_k$, 그리고 $$\max\{\min\{x_i : i \in S_1\}, \min\{x_i : i \in S_2\}, \dots, \min\{x_i : i \in S_k\}\}.$$ 생성되는 값은 항상 최대 $k$별개의 요소, 그래서 그건 적어도$k^{\text{th}}$최소. 그리고 만약$k$ 가장 작은 요소가 $S_1, \dots, S_k$다음 절의 값 입니다$k^{\text{th}}$ 가장 작은 요소.
항상 이런 일이 발생하도록하기 위해 무작위로 많은 절을 생성합니다. $i \in \{1,2,\dots,m\}$, 우리는 (독립적이고 균일하게 무작위로) 선택하여 다음 중 하나에 넣습니다. $S_1, \dots, S_k$. 연결된 Math.SE 답변에서 볼 수 있듯이$\frac{k^k}{k!} \ln \binom mk \approx k e^k \ln m$절, 그러면 양의 확률로 모든 $k$변수를 구분하는 절이 있습니다. 이 경우 최종 공식은이 모든 절의 최소값이됩니다.
여기에 또 다른 접근 방식이 있습니다. 그것은 종류의 사이에 위치 의 athin @ 및 @Jan 이반의 방법.
두 번째로 작은 숫자가
다른 숫자보다 크거나 같은 가장 작은 숫자.
이것은 우리가 할 수 있음을 의미합니다
가능한 모든 쌍별 max ()에 대한 min () : $$\min\left(\max(x_1, x_2), \max(x_1,x_3),\ldots, \max(x_{m-1}, x_m)\right)$$
이것이 작동하는지 다시 한 번 확인하려면
가장 작은 숫자에 대한 동점이없는 한, 가장 작은 숫자는 절대 max () es 중 하나로 나타나지 않을 것입니다. 이것은 우리 가 보여주고 싶은 특별한 경우 입니다.