Menu
I am trying to solve this problem..
Given a list of n numbers, we would like to find the smallest and the second smallest numbers from the list. Describe a divide-and-conquer algorithm to solve this problem. Assume that n = 2^k for an integer k. The number of comparisons using your algorithm should not be more than 3n/2 − 2, even in the worst case.
My current solution is to use select algorithm to get the median and then divide the list into L1( contains element less than or equal to the median), R ( median), L2 ( contains all the elements grater than median). Is it correct? If so, what should I do next?
632
Another way that we can find the second smallest number in a list of numbers is with sorting. We can sort a list in ascending order, and we then know that the smallest number is the first number of the sorted list, the second smallest number is the second number, and so on. We can access the second element of a list by accessing the ‘1’ position.
Find the smallest and second smallest elements in an array. Write an efficient C program to find smallest and second smallest element in an array. Example: Input: arr[] = {12, 13, 1, 10, 34, 1} Output: The smallest element is 1 and second Smallest element is 10. A Simple Solution is to sort the array in increasing order.
From the above Python Program to find the Largest and Smallest Number in a List screenshot, you can observe that the User inserted values are NumList = {40, 60, 20, 11, 50} smallest = largest = NumList = 40 First Iteration – for 1 in range (1, 5) – Condition is true
In first traversal find the minimum element. Let this element be x. In second traversal, find the smallest element greater than x. Time complexity of this solution is O (n). The above solution requires two traversals of input array. An Efficient Solution can find the minimum two elements in one traversal.
Note that the median-selection algorithm uses Θ(n) comparisons, but that doesn't mean that it uses at most 3n/2 - 2 comparisons. In fact, I think it uses a lot more, which probably rules out your solution strategy.
As a hint: think of this problem as building an elimination tournament for all 2k; the winner of each round (the smaller of the two numbers) advances to the next. How many comparisons are needed to implement that? Next, notice that the second-smallest number must have "lost" to the smallest number. The second-smallest number is also the smallest number that "lost" to the smallest number. Given this, could you efficiently find the second-smallest number?
Hope this helps!
132
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
