Timeline for Finding Second Largest Element in an Array
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 18, 2017 at 8:58 | comment | added | Incomputable | @greybeard, edited. Hopefully now it is correct. | |
| Dec 18, 2017 at 8:58 | history | edited | Incomputable | CC BY-SA 3.0 |
added 2 characters in body
|
| Dec 17, 2017 at 21:48 | comment | added | Incomputable | @greybeard, ah, I see. I always perform extra check. Now I totally got it. I’ll edit it tomorrow | |
| Dec 17, 2017 at 16:45 | comment | added | Incomputable |
@KalKaraman, C++ has standard library algorithms. The code could be tinier if it utilized those algorithms. Also, it binds people to pointers of int, and passing size. It also forces index based access, which is not available in std::list, or std::map and similar.
|
|
| Dec 17, 2017 at 16:39 | comment | added | Incomputable | @KalKaraman, It is linear. As mentioned above, one cannot get faster than linear since they need to look at all of the elements. | |
| Dec 17, 2017 at 16:35 | comment | added | Ahmed Karaman | @Incomputable what would be the time complexity of your solution ? I also didn't get what you mean by saying Using C++ as C. | |
| Dec 17, 2017 at 9:22 | comment | added | Incomputable | @greybeard, I somewhat I understand it better now, but I'll try to benchmark it later. | |
| Dec 17, 2017 at 9:19 | history | edited | Incomputable | CC BY-SA 3.0 |
deleted 37 characters in body
|
| Dec 16, 2017 at 22:56 | comment | added | Incomputable | @KennyOstrom, I actually got really interested in this. I’ll try to post benchmark tomorrow. I’m sure you’re right, I just want to test to what extent. I’ll post it as different answer, so you could +1 me again xD. On a more serious note, I think it conceptually differs from this post. | |
| Dec 16, 2017 at 22:48 | comment | added | Kenny Ostrom | I was only considering comparisons. Given randomized input, the chance that the next value will be the new maximum is low, and goes down dramatically over time. The chance that the next value will be third or lower is high and goes up. You want to shortcut on the case that the next value is less than the current second greatest, to cut comparisons almost in half. On the other hand, you minimize swap/move operations, but that's trivial on int. I already did +1 though, nice answer. | |
| Dec 16, 2017 at 22:46 | comment | added | Incomputable | @KennyOstrom, fixed. Now it looks a lot nicer. Thanks | |
| Dec 16, 2017 at 22:46 | history | edited | Incomputable | CC BY-SA 3.0 |
deleted 62 characters in body
|
| Dec 16, 2017 at 22:34 | comment | added | Incomputable | @KennyOstrom, I’m going to sleep, but the second point is pretty legit. I’ll fix it tomorrow, but if you want you can edit it now. The first point makes assumptions about input pattern :) | |
| Dec 16, 2017 at 22:30 | comment | added | Kenny Ostrom | Not a big deal, but I would compare to greatest2 first. It is more likely to shortcut the next comparison, and I prefer using if ... else over continue. Also that while look looks a lot like an expanded for loop. | |
| Dec 16, 2017 at 21:42 | history | edited | Incomputable | CC BY-SA 3.0 |
added 180 characters in body
|
| Dec 16, 2017 at 21:32 | history | answered | Incomputable | CC BY-SA 3.0 |