Author |
Topic: second largest number (Read 2171 times) |
|
davidderrick
Newbie
Gender: 
Posts: 9
|
 |
second largest number
« on: Mar 14th, 2010, 3:01pm » |
 Quote  Modify
|
First greater number in an array. Given a large array of positive integers,
for an arbitrary integer A, we want to know the first integer in the array
which is greater than or equal A . O(logn) solution required
ex [2, 10,5,6,80]
input : 6 output : 10
input :20 output : 80
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: second largest number
« Reply #1 on: Mar 14th, 2010, 3:38pm » |
Quote Modify
|
Unless the array is sorted or something, I don't see that happening. If you haven't looked at all the integers in the array, you can never be certain you're not ignoring the one that is the "next larger" one.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Ved
Junior Member
Gender:
Posts: 53
|
|
Re: second largest number
« Reply #2 on: Feb 7th, 2012, 4:23am » |
Quote Modify
|
In that case - what is the o(n) best case solution ? just to complete this thread.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: second largest number
« Reply #3 on: Feb 7th, 2012, 5:19am » |
Quote Modify
|
Hmm, the topic and the question asked don't seem to have anything to do with one another. For completeness, three different answers. 
1) Find the second-largest element in an unsorted array in O(n)
int secondLargest(int[] arr) {
if (arr.length < 2) throw new IllegalArgumentException("Too few elements");
int largest = Integer.MIN_VALUE, nextLargest = Integer.MIN_VALUE;
for(int i = 0; i < arr.length; ++i) {
if (arr[i] > largest) {
nextLargest = largest;
largest = arr[i];
} else if (arr[i] > nextLargest) {
nextLargest = arr[i];
}
}
return nextLargest;
}
2) Find the first element greater than k in an unsorted array in O(n)
int firstGreaterUnsorted(int[] arr, int k) {
for(int i = 0; i < arr.length; ++i) {
if (arr[i] > k) return arr[i];
}
throw new IllegalArgumentException("No such element");
}
3) Fint the first element greater than k in a sorted array in O(log n)
int firstGreaterSorted(int[] arr, int k) {
// binary search of increasing array
int first = 0, mid = arr.length/2, last = arr.length;
while (mid > first && arr[mid] != k) {
if (arr[mid]) first = mid; else last = mid;
mid = first + (last - first)/2;
}
if (arr[mid] <= k) ++mid;
if (mid == arr.length) throw new IllegalArgumentException("No such element");
return arr[mid];
}
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print