Difference between revisions of "TADM2E 4.2"
From Algorithm Wiki
Letientai299 (talk | contribs) |
Landisdesign (talk | contribs) m (Clarified (d)) |
||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
| − | (a) | + | (a) Iterate over the array once, keeping track of the max and min values respectively for x and y. This will have <math>O(n)</math> worst-case time. |
(b) The answer is straight forward: <math>S[1]</math> and <math>S[n],</math> since they are the two extreme values. | (b) The answer is straight forward: <math>S[1]</math> and <math>S[n],</math> since they are the two extreme values. | ||
| Line 5: | Line 5: | ||
(c) Sort the array with any <math>n\log(n)</math> method. Then scan through the sorted array to find the smallest gap, thus the desired pair. | (c) Sort the array with any <math>n\log(n)</math> method. Then scan through the sorted array to find the smallest gap, thus the desired pair. | ||
| − | (d) Same as | + | (d) Same as (c), after sorting. |
Latest revision as of 23:57, 20 November 2019
(a) Iterate over the array once, keeping track of the max and min values respectively for x and y. This will have $ O(n) $ worst-case time.
(b) The answer is straight forward: $ S[1] $ and $ S[n], $ since they are the two extreme values.
(c) Sort the array with any $ n\log(n) $ method. Then scan through the sorted array to find the smallest gap, thus the desired pair.
(d) Same as (c), after sorting.
