Find the 2nd largest element in an array with minimum number of comparisons
F开发者_C百科or an array of size N, what is the number of comparisons required?
The optimal algorithm uses n+log n-2 comparisons. Think of elements as competitors, and a tournament is going to rank them.
First, compare the elements, as in the tree
|
/ \
| |
/ \ / \
x x x x
this takes n-1 comparisons and each element is involved in comparison at most log n times. You will find the largest element as the winner.
The second largest element must have lost a match to the winner (he can't lose a match to a different element), so he's one of the log n elements the winner has played against. You can find which of them using log n - 1 comparisons.
The optimality is proved via adversary argument. See https://math.stackexchange.com/questions/1601 or http://compgeom.cs.uiuc.edu/~jeffe/teaching/497/02-selection.pdf or http://www.imada.sdu.dk/~jbj/DM19/lb06.pdf or https://www.utdallas.edu/~chandra/documents/6363/lbd.pdf
You can find the second largest value with at most 2·(N-1) comparisons and two variables that hold the largest and second largest value:
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;
Use Bubble sort or Selection sort algorithm which sorts the array in descending order. Don't sort the array completely. Just two passes. First pass gives the largest element and second pass will give you the second largest element.
No. of comparisons for first pass: n-1
No. of comparisons for second pass: n-2
Total no. of comparison for finding second largest: 2n-3
May be you can generalize this algorithm. If you need the 3rd largest then you make 3 passes.
By above strategy you don't need any temporary variables as Bubble sort and Selection sort are in place sorting algorithms.
Here is some code that might not be optimal but at least actually finds the 2nd largest element:
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 ];
}
}
}
It needs at least N-1 comparisons if the largest 2 elements are at the beginning of the array and at most 2N-3 in the worst case (one of the first 2 elements is the smallest in the array).
case 1-->9 8 7 6 5 4 3 2 1
case 2--> 50 10 8 25 ........
case 3--> 50 50 10 8 25.........
case 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];
}
}
Sorry, JS code...
Tested with the two inputs:
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
This should have a maximum of a.length*2 comparisons and only goes through the list once.
I know this is an old question, but here is my attempt at solving it, making use of the Tournament Algorithm. It is similar to the solution used by @sdcvvc , but I am using two-dimensional array to store elements.
To make things work, there are two assumptions:
1) number of elements in the array is the power of 2
2) there are no duplicates in the array
The whole process consists of two steps:
1. building a 2D array by comparing two by two elements. First row in the 2D array is gonna be the entire input array. Next row contains results of the comparisons of the previous row. We continue comparisons on the newly built array and keep building the 2D array until an array of only one element (the largest one) is reached.
2. we have a 2D-array where last row contains only one element: the largest one. We continue going from the bottom to the top, in each array finding the element that was "beaten" by the largest and comparing it to the current "second largest" value. To find the element beaten by the largest, and to avoid O(n) comparisons, we must store the index of the largest element in the previous row. That way we can easily check the adjacent elements. At any level (above root level),the adjacent elements are obtained as:
leftAdjacent = rootIndex*2
rightAdjacent = rootIndex*2+1,
where rootIndex is index of the largest(root) element at the previous level.
I know the question asks for C++, but here is my attempt at solving it in Java. (I've used lists instead of arrays, to avoid messy changing of the array size and/or unnecessary array size calculations)
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;
}
Suppose provided array is inPutArray = [1,2,5,8,7,3] expected O/P -> 7 (second largest)
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])
PHP version of the Gumbo algorithm: 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";
Assuming space is irrelevant, this is the smallest I could get it. It requires 2*n comparisons in worst case, and n comparisons in best case:
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]
try this.
max1 = a[0].
max2.
for i = 0, until length:
if a[i] > max:
max2 = max1.
max1 = a[i].
#end IF
#end FOR
return min2.
it should work like a charm. low in complexity.
here is a java code.
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()
Use counting sort and then find the second largest element, starting from index 0 towards the end. There should be at least 1 comparison, at most n-1 (when there's only one element!).
#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);
}
The accepted solution by sdcvvc in C++11.
#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;
}
I have gone through all the posts above but I am convinced that the implementation of the Tournament algorithm is the best approach. Let us consider the following algorithm posted by @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;
It is very good in case we are going to find the second largest number in an array. It has (2n-1) number of comparisons. But what if you want to calculate the third largest number or some kth largest number. The above algorithm doesn't work. You got to another procedure.
So, I believe tournament algorithm approach is the best and here is the link for that.
The following solution would take 2(N-1) comparisons:
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
It can be done in n + ceil(log n) - 2 comparison.
Solution: it takes n-1 comparisons to get minimum.
But to get minimum we will build a tournament in which each element will be grouped in pairs. like a tennis tournament and winner of any round will go forward.
Height of this tree will be log n since we half at each round.
Idea to get second minimum is that it will be beaten by minimum candidate in one of previous round. So, we need to find minimum in potential candidates (beaten by minimum).
Potential candidates will be log n = height of tree
So, no. of comparison to find minimum using tournament tree is n-1 and for second minimum is log n -1 sums up = n + ceil(log n) - 2
Here is C++ code
#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];
Ref: http://www.ajaybadgujar.com/finding-second-largest-number-from-array-in-javascript/
A good way with O(1) time complexity would be to use a max-heap. Call the heapify twice and you have the answer.
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
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);
}
}
Sort the array into ascending order then assign a variable to the (n-1)th term.
加载中,请稍侯......
精彩评论