Problem Detail: I have an algorithmic problem. Given an array (or a set) $T$ of $n$ nonnegative integers. Find the maximal set $S$ of $T$ such that for all $ain S$, $ageqslant |S|$. For example:
- If $T$=[1, 3, 4, 1, 3, 6], then $S$ can be [3, 3, 6] or [3, 4, 6] or [4, 3, 6].
- In $T$=[7, 5, 1, 1, 7, 4], then $S$ is [7, 5, 7, 4].
I have tried this recursive function.
function(T): if minimum(T) >= length(T): return T else: return function(Tminimum(T))
Is there any non-recursive algorithm. (I did not check my recursive algorithm, so it could has some flaw.)
Asked By : Azzo
Answered By : Karolis Juodelė
Sort T. Then take elements while T[i] >= i+1. For example sorted(T)=[6,4,3,3,1,1]. Then, T[0] = 6 > 1, T[1] = 4 > 2, T[2] = 3 <= 3 and finally, T[3] = 3 < 4 so we have S = [T[0], T[1], T[2]].
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/66048
