최소 비교 횟수로 배열에서 두 번째로 큰 요소 찾기
크기가 N 인 배열의 경우 필요한 비교 횟수는 얼마입니까?
최적의 알고리즘은 n + log n-2 비교를 사용합니다. 요소를 경쟁자로 생각하면 토너먼트에서 순위를 매길 것입니다.
먼저 트리에서와 같이 요소를 비교하십시오.
|
/ \
| |
/ \ / \
x x x x
이것은 n-1 개의 비교를 필요로하며 각 요소는 최대 log n 번의 비교에 포함됩니다. 가장 큰 요소를 승자로 찾을 수 있습니다.
두 번째로 큰 요소는 승자와의 경기에서 패 했음에 틀림 없으므로 (다른 요소와의 경기에서 패할 수 없음) 그는 승자가 대항 한 log n 요소 중 하나입니다. log n-1 비교를 사용하여 그중 어떤 것을 찾을 수 있습니다.
최적 성은 적대적인 주장을 통해 입증됩니다. https://math.stackexchange.com/questions/1601 또는 http://compgeom.cs.uiuc.edu/~jeffe/teaching/497/02-selection.pdf 또는 http : //www.imada.sdu를 참조 하십시오 . dk / ~ jbj / DM19 / lb06.pdf 또는 https://www.utdallas.edu/~chandra/documents/6363/lbd.pdf
최대 2 · ( N -1) 비교와 가장 큰 값과 두 번째로 큰 값을 보유하는 두 개의 변수로 두 번째로 큰 값을 찾을 수 있습니다 .
largest := numbers[0];
secondLargest := null
for i=1 to numbers.length-1 do
number := numbers[i];
if number > largest then
secondLargest := largest;
largest := number;
else
if number > secondLargest then
secondLargest := number;
end;
end;
end;
배열을 내림차순으로 정렬하는 버블 정렬 또는 선택 정렬 알고리즘을 사용합니다. 배열을 완전히 정렬하지 마십시오. 두 번만 통과합니다. 첫 번째 패스는 가장 큰 요소를 제공하고 두 번째 패스는 두 번째로 큰 요소를 제공합니다.
첫 번째 통과 비교 횟수 : n-1
첫 번째 통과 비교 횟수 : n-2
총 아니. 두 번째로 큰 것을 찾기위한 비교 : 2n-3
이 알고리즘을 일반화 할 수 있습니다. 세 번째로 큰 것이 필요하면 3 번 통과합니다.
위의 전략에 따르면 거품 정렬 및 선택 정렬이 제자리 정렬 알고리즘에 있으므로 임시 변수가 필요하지 않습니다 .
다음은 최적이 아닐 수도 있지만 적어도 실제로 두 번째로 큰 요소를 찾는 코드입니다.
if( val[ 0 ] > val[ 1 ] )
{
largest = val[ 0 ]
secondLargest = val[ 1 ];
}
else
{
largest = val[ 1 ]
secondLargest = val[ 0 ];
}
for( i = 2; i < N; ++i )
{
if( val[ i ] > secondLargest )
{
if( val[ i ] > largest )
{
secondLargest = largest;
largest = val[ i ];
}
else
{
secondLargest = val[ i ];
}
}
}
가장 큰 2 개의 요소가 배열의 시작 부분에 있고 최악의 경우 2N-3 개 이하인 경우 최소 N-1 개의 비교가 필요합니다 (처음 2 개 요소 중 하나가 배열에서 가장 작음).
사례 1-> 98 7 6 5 4 3 2 1
사례 2-> 50 10 8 25 ........
사례 3-> 50 50 10 8 25 .........
사례 4-> 50 50 10 8 50 25 .......
public void second element()
{
int a[10],i,max1,max2;
max1=a[0],max2=a[1];
for(i=1;i<a.length();i++)
{
if(a[i]>max1)
{
max2=max1;
max1=a[i];
}
else if(a[i]>max2 &&a[i]!=max1)
max2=a[i];
else if(max1==max2)
max2=a[i];
}
}
죄송합니다. JS 코드 ...
두 가지 입력으로 테스트되었습니다.
a = [55,11,66,77,72];
a = [ 0, 12, 13, 4, 5, 32, 8 ];
var first = Number.MIN_VALUE;
var second = Number.MIN_VALUE;
for (var i = -1, len = a.length; ++i < len;) {
var dist = a[i];
// get the largest 2
if (dist > first) {
second = first;
first = dist;
} else if (dist > second) { // && dist < first) { // this is actually not needed, I believe
second = dist;
}
}
console.log('largest, second largest',first,second);
largest, second largest 32 13
이것은 최대 a.length * 2 비교를 가져야하며 목록을 한 번만 통과합니다.
나는 이것이 오래된 질문이라는 것을 알고 있지만 토너먼트 알고리즘을 사용하여 해결하려는 시도입니다. @sdcvvc에서 사용하는 솔루션과 유사하지만 요소를 저장하기 위해 2 차원 배열을 사용하고 있습니다.
작업을 수행하기 위해 두 가지 가정이 있습니다.
1) 배열의 요소 수는 2의 거듭 제곱입니다.
2) 배열에 중복 항목이 없습니다.
전체 프로세스는 두 단계로 구성됩니다.
1. 두 요소를 두 요소로 비교하여 2D 배열을 만듭니다. 2D 배열의 첫 번째 행은 전체 입력 배열이됩니다. 다음 행에는 이전 행의 비교 결과가 포함됩니다. 새로 빌드 된 배열에 대한 비교를 계속하고 하나의 요소 (가장 큰 요소)의 배열에 도달 할 때까지 2D 배열을 계속 빌드합니다.
2. 마지막 행에 가장 큰 요소 하나만 포함 된 2D 배열이 있습니다. 우리는 계속해서 아래에서 위로 이동하여 각 배열에서 가장 큰 요소에 의해 "두드린"요소를 찾아 현재 "두 번째로 큰"값과 비교합니다. 가장 큰 요소를 찾고 O (n) 비교를 피하기 위해 이전 행에 가장 큰 요소의 인덱스를 저장해야합니다. 이렇게하면 인접한 요소를 쉽게 확인할 수 있습니다. 모든 수준 (루트 수준 이상)에서 인접한 요소는 다음과 같이 얻습니다.
leftAdjacent = rootIndex*2
rightAdjacent = rootIndex*2+1,
여기서 rootIndex는 이전 수준에서 가장 큰 (루트) 요소의 인덱스입니다.
질문이 C ++를 요구한다는 것을 알고 있지만 여기에 Java로 해결하려는 시도가 있습니다. (배열 크기 변경 및 / 또는 불필요한 배열 크기 계산을 피하기 위해 배열 대신 목록을 사용했습니다)
public static Integer findSecondLargest(List<Integer> list) {
if (list == null) {
return null;
}
if (list.size() == 1) {
return list.get(0);
}
List<List<Integer>> structure = buildUpStructure(list);
System.out.println(structure);
return secondLargest(structure);
}
public static List<List<Integer>> buildUpStructure(List<Integer> list) {
List<List<Integer>> newList = new ArrayList<List<Integer>>();
List<Integer> tmpList = new ArrayList<Integer>(list);
newList.add(tmpList);
int n = list.size();
while (n>1) {
tmpList = new ArrayList<Integer>();
for (int i = 0; i<n; i=i+2) {
Integer i1 = list.get(i);
Integer i2 = list.get(i+1);
tmpList.add(Math.max(i1, i2));
}
n/= 2;
newList.add(tmpList);
list = tmpList;
}
return newList;
}
public static Integer secondLargest(List<List<Integer>> structure) {
int n = structure.size();
int rootIndex = 0;
Integer largest = structure.get(n-1).get(rootIndex);
List<Integer> tmpList = structure.get(n-2);
Integer secondLargest = Integer.MIN_VALUE;
Integer leftAdjacent = -1;
Integer rightAdjacent = -1;
for (int i = n-2; i>=0; i--) {
rootIndex*=2;
tmpList = structure.get(i);
leftAdjacent = tmpList.get(rootIndex);
rightAdjacent = tmpList.get(rootIndex+1);
if (leftAdjacent.equals(largest)) {
if (rightAdjacent > secondLargest) {
secondLargest = rightAdjacent;
}
}
if (rightAdjacent.equals(largest)) {
if (leftAdjacent > secondLargest) {
secondLargest = leftAdjacent;
}
rootIndex=rootIndex+1;
}
}
return secondLargest;
}
제공된 배열이 inPutArray = [1,2,5,8,7,3] 예상 O / P-> 7 (두 번째로 큰 값)이라고 가정합니다.
take temp array
temp = [0,0], int dummmy=0;
for (no in inPutArray) {
if(temp[1]<no)
temp[1] = no
if(temp[0]<temp[1]){
dummmy = temp[0]
temp[0] = temp[1]
temp[1] = temp
}
}
print("Second largest no is %d",temp[1])
Gumbo 알고리즘의 PHP 버전 : http://sandbox.onlinephpfunctions.com/code/51e1b05dac2e648fd13e0b60f44a2abe1e4a8689
$numbers = [10, 9, 2, 3, 4, 5, 6, 7];
$largest = $numbers[0];
$secondLargest = null;
for ($i=1; $i < count($numbers); $i++) {
$number = $numbers[$i];
if ($number > $largest) {
$secondLargest = $largest;
$largest = $number;
} else if ($number > $secondLargest) {
$secondLargest = $number;
}
}
echo "largest=$largest, secondLargest=$secondLargest";
공간이 무관하다고 가정하면 이것이 내가 얻을 수있는 가장 작은 공간입니다. 최악의 경우 2 * n 비교, 최상의 경우 n 비교가 필요합니다.
arr = [ 0, 12, 13, 4, 5, 32, 8 ]
max = [ -1, -1 ]
for i in range(len(arr)):
if( arr[i] > max[0] ):
max.insert(0,arr[i])
elif( arr[i] > max[1] ):
max.insert(1,arr[i])
print max[1]
이 시도.
max1 = a[0].
max2.
for i = 0, until length:
if a[i] > max:
max2 = max1.
max1 = a[i].
#end IF
#end FOR
return min2.
매력처럼 작동해야합니다. 복잡성이 낮습니다.
여기에 자바 코드가 있습니다.
int secondlLargestValue(int[] secondMax){
int max1 = secondMax[0]; // assign the first element of the array, no matter what, sorted or not.
int max2 = 0; // anything really work, but zero is just fundamental.
for(int n = 0; n < secondMax.length; n++){ // start at zero, end when larger than length, grow by 1.
if(secondMax[n] > max1){ // nth element of the array is larger than max1, if so.
max2 = max1; // largest in now second largest,
max1 = secondMax[n]; // and this nth element is now max.
}//end IF
}//end FOR
return max2;
}//end secondLargestValue()
계수 정렬을 사용하고 인덱스 0부터 끝까지 두 번째로 큰 요소를 찾습니다. 최소한 하나의 비교가 있어야합니다 n-1(요소가 하나 뿐인 경우!).
#include<stdio.h>
main()
{
int a[5] = {55,11,66,77,72};
int max,min,i;
int smax,smin;
max = min = a[0];
smax = smin = a[0];
for(i=0;i<=4;i++)
{
if(a[i]>max)
{
smax = max;
max = a[i];
}
if(max>a[i]&&smax<a[i])
{
smax = a[i];
}
}
printf("the first max element z %d\n",max);
printf("the second max element z %d\n",smax);
}
C ++ 11에서 sdcvvc가 허용하는 솔루션입니다.
#include <algorithm>
#include <iostream>
#include <vector>
#include <cassert>
#include <climits>
using std::vector;
using std::cout;
using std::endl;
using std::random_shuffle;
using std::min;
using std::max;
vector<int> create_tournament(const vector<int>& input) {
// make sure we have at least two elements, so the problem is interesting
if (input.size() <= 1) {
return input;
}
vector<int> result(2 * input.size() - 1, -1);
int i = 0;
for (const auto& el : input) {
result[input.size() - 1 + i] = el;
++i;
}
for (uint j = input.size() / 2; j > 0; j >>= 1) {
for (uint k = 0; k < 2 * j; k += 2) {
result[j - 1 + k / 2] = min(result[2 * j - 1 + k], result[2 * j + k]);
}
}
return result;
}
int second_smaller(const vector<int>& tournament) {
const auto& minimum = tournament[0];
int second = INT_MAX;
for (uint j = 0; j < tournament.size() / 2; ) {
if (tournament[2 * j + 1] == minimum) {
second = min(second, tournament[2 * j + 2]);
j = 2 * j + 1;
}
else {
second = min(second, tournament[2 * j + 1]);
j = 2 * j + 2;
}
}
return second;
}
void print_vector(const vector<int>& v) {
for (const auto& el : v) {
cout << el << " ";
}
cout << endl;
}
int main() {
vector<int> a;
for (int i = 1; i <= 2048; ++i)
a.push_back(i);
for (int i = 0; i < 1000; i++) {
random_shuffle(a.begin(), a.end());
const auto& v = create_tournament(a);
assert (second_smaller(v) == 2);
}
return 0;
}
위의 모든 게시물을 검토했지만 토너먼트 알고리즘의 구현이 최선의 접근 방식이라고 확신합니다. @Gumbo가 게시 한 다음 알고리즘을 고려해 보겠습니다.
largest := numbers[0];
secondLargest := null
for i=1 to numbers.length-1 do
number := numbers[i];
if number > largest then
secondLargest := largest;
largest := number;
else
if number > secondLargest then
secondLargest := number;
end;
end;
end;
배열에서 두 번째로 큰 숫자를 찾을 경우 매우 좋습니다. 비교 횟수는 (2n-1)입니다. 그러나 세 번째로 큰 숫자 나 k 번째로 큰 숫자를 계산하려면 어떻게해야합니까? 위의 알고리즘은 작동하지 않습니다. 다른 절차를 밟았습니다.
그래서 저는 토너먼트 알고리즘 접근 방식이 최고라고 믿으며 여기에 그 링크 가 있습니다.
다음 솔루션은 2 (N-1) 비교를 수행합니다.
arr #array with 'n' elements
first=arr[0]
second=-999999 #large negative no
i=1
while i is less than length(arr):
if arr[i] greater than first:
second=first
first=arr[i]
else:
if arr[i] is greater than second and arr[i] less than first:
second=arr[i]
i=i+1
print second
n + ceil (log n)-2 비교로 수행 할 수 있습니다.
솔루션 : 최소값을 얻으려면 n-1 비교가 필요합니다.
그러나 최소한으로하기 위해 각 요소가 쌍으로 그룹화되는 토너먼트를 구축 할 것입니다. 테니스 토너먼트처럼 모든 라운드의 승자가 진행됩니다.
이 나무의 높이는 우리가 각 라운드에서 절반이므로 log n이 될 것입니다.
두 번째 최소값을 얻으려는 아이디어는 이전 라운드 중 하나에서 최소 후보자에게 이길 것이라는 것입니다. 따라서 우리는 잠재적 인 후보자에서 최소값을 찾아야합니다.
잠재적 후보는 log n = 나무 높이입니다.
그래서 아니야. 토너먼트 트리를 사용하여 최소값을 찾는 비교는 n-1이고 두 번째 최소값은 logn -1 sums up = n + ceil (log n)-2
다음은 C ++ 코드입니다.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
using namespace std;
typedef pair<int,int> ii;
bool isPowerOfTwo (int x)
{
/* First x in the below expression is for the case when x is 0 */
return x && (!(x&(x-1)));
}
// modified
int log_2(unsigned int n) {
int bits = 0;
if (!isPowerOfTwo(n))
bits++;
if (n > 32767) {
n >>= 16;
bits += 16;
}
if (n > 127) {
n >>= 8;
bits += 8;
}
if (n > 7) {
n >>= 4;
bits += 4;
}
if (n > 1) {
n >>= 2;
bits += 2;
}
if (n > 0) {
bits++;
}
return bits;
}
int second_minima(int a[], unsigned int n) {
// build a tree of size of log2n in the form of 2d array
// 1st row represents all elements which fights for min
// candidate pairwise. winner of each pair moves to 2nd
// row and so on
int log_2n = log_2(n);
long comparison_count = 0;
// pair of ints : first element stores value and second
// stores index of its first row
ii **p = new ii*[log_2n];
int i, j, k;
for (i = 0, j = n; i < log_2n; i++) {
p[i] = new ii[j];
j = j&1 ? j/2+1 : j/2;
}
for (i = 0; i < n; i++)
p[0][i] = make_pair(a[i], i);
// find minima using pair wise fighting
for (i = 1, j = n; i < log_2n; i++) {
// for each pair
for (k = 0; k+1 < j; k += 2) {
// find its winner
if (++comparison_count && p[i-1][k].first < p[i-1][k+1].first) {
p[i][k/2].first = p[i-1][k].first;
p[i][k/2].second = p[i-1][k].second;
}
else {
p[i][k/2].first = p[i-1][k+1].first;
p[i][k/2].second = p[i-1][k+1].second;
}
}
// if no. of elements in row is odd the last element
// directly moves to next round (row)
if (j&1) {
p[i][j/2].first = p[i-1][j-1].first;
p[i][j/2].second = p[i-1][j-1].second;
}
j = j&1 ? j/2+1 : j/2;
}
int minima, second_minima;
int index;
minima = p[log_2n-1][0].first;
// initialize second minima by its final (last 2nd row)
// potential candidate with which its final took place
second_minima = minima == p[log_2n-2][0].first ? p[log_2n-2][1].first : p[log_2n-2][0].first;
// minima original index
index = p[log_2n-1][0].second;
for (i = 0, j = n; i <= log_2n - 3; i++) {
// if its last candidate in any round then there is
// no potential candidate
if (j&1 && index == j-1) {
index /= 2;
j = j/2+1;
continue;
}
// if minima index is odd, then it fighted with its index - 1
// else its index + 1
// this is a potential candidate for second minima, so check it
if (index&1) {
if (++comparison_count && second_minima > p[i][index-1].first)
second_minima = p[i][index-1].first;
}
else {
if (++comparison_count && second_minima > p[i][index+1].first)
second_minima = p[i][index+1].first;
}
index/=2;
j = j&1 ? j/2+1 : j/2;
}
printf("-------------------------------------------------------------------------------\n");
printf("Minimum : %d\n", minima);
printf("Second Minimum : %d\n", second_minima);
printf("comparison count : %ld\n", comparison_count);
printf("Least No. Of Comparisons (");
printf("n+ceil(log2_n)-2) : %d\n", (int)(n+ceil(log(n)/log(2))-2));
return 0;
}
int main()
{
unsigned int n;
scanf("%u", &n);
int a[n];
int i;
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
second_minima(a,n);
return 0;
}
function findSecondLargeNumber(arr){
var fLargeNum = 0;
var sLargeNum = 0;
for(var i=0; i<arr.length; i++){
if(fLargeNum < arr[i]){
sLargeNum = fLargeNum;
fLargeNum = arr[i];
}else if(sLargeNum < arr[i]){
sLargeNum = arr[i];
}
}
return sLargeNum;
}
var myArray = [799, -85, 8, -1, 6, 4, 3, -2, -15, 0, 207, 75, 785, 122, 17];
참조 : http://www.ajaybadgujar.com/finding-second-largest-number-from-array-in-javascript/
O (1) 시간 복잡성을 사용하는 좋은 방법은 최대 힙을 사용하는 것입니다. heapify를 두 번 호출하면 답이 있습니다.
int[] int_array = {4, 6, 2, 9, 1, 7, 4, 2, 9, 0, 3, 6, 1, 6, 8};
int largst=int_array[0];
int second=int_array[0];
for (int i=0; i<int_array.length; i++){
if(int_array[i]>largst) {
second=largst;
largst=int_array[i];
}
else if(int_array[i]>second && int_array[i]<largst) {
second=int_array[i];
}
}
I suppose, follow the "optimal algorithm uses n+log n-2 comparisons" from above, the code that I came up with that doesn't use binary tree to store the value would be the following:
During each recursive call, the array size is cut in half.
So the number of comparison is:
1st iteration: n/2 comparisons
2nd iteration: n/4 comparisons
3rd iteration: n/8 comparisons
... Up to log n iterations?
Hence, total => n - 1 comparisons?
function findSecondLargestInArray(array) {
let winner = [];
if (array.length === 2) {
if (array[0] < array[1]) {
return array[0];
} else {
return array[1];
}
}
for (let i = 1; i <= Math.floor(array.length / 2); i++) {
if (array[2 * i - 1] > array[2 * i - 2]) {
winner.push(array[2 * i - 1]);
} else {
winner.push(array[2 * i - 2]);
}
}
return findSecondLargestInArray(winner);
}
Assuming array contain 2^n number of numbers.
If there are 6 numbers, then 3 numbers will move to the next level, which is not right.
Need like 8 numbers => 4 number => 2 number => 1 number => 2^n number of number
Sort the array into ascending order then assign a variable to the (n-1)th term.
class solution:
def SecondLargestNumber (self,l):
Largest = 0
secondLargest = 0
for i in l:
if i> Largest:
secondLargest = Largest
Largest = max(Largest, i)
return Largest, secondLargest
package com.array.orderstatistics;
import java.util.Arrays;
import java.util.Collections;
public class SecondLargestElement {
/**
* Total Time Complexity will be n log n + O(1)
* @param str
*/
public static void main(String str[]) {
Integer[] integerArr = new Integer[] { 5, 1, 2, 6, 4 };
// Step1 : Time Complexity will be n log(n)
Arrays.sort(integerArr, Collections.reverseOrder());
// Step2 : Array.get Second largestElement
int secondLargestElement = integerArr[1];
System.out.println(secondLargestElement);
}
}
'Program Tip' 카테고리의 다른 글
| transform (rotate) 설정으로 Z-index가 취소됩니다. (0) | 2020.11.17 |
|---|---|
| Git 커밋 트리밍 / Git 기록 스 쿼싱 (0) | 2020.11.17 |
| 콘솔 응용 프로그램의 경우 "종료시" (0) | 2020.11.17 |
| 기존 DataTable에 값이있는 새 열을 추가하는 방법은 무엇입니까? (0) | 2020.11.17 |
| EditText 상자 높이를 확장하는 방법 (0) | 2020.11.16 |