Maximum K

Let M(k) = true denote there are at least k elements in a given array larger than or equal to k. Find the maximum k such that M(k) = true.

For example:

{1, 3, 2, 6, 9}, there are 3 elements larger than or equal to 3. Maximum k = 3.
{1, 3, 4, 6, 9},  there are 4 elements larger than or equal to 3. Maximum k = 3;
{1,1,1}, there are 3 elements larger than or equal to 1. Maximum k = 1;

Analysis:

Suppose the array A is sorted for largest to smallest.

1) A[i] > i means that all elements from 0 to i are larger than or equal to i. Maximum k >= i.
2) A[i] == i means that A[i+1] < i+1, thus maximum k = i
3) A[i-1] > i-1 && A[i] < i. From A[i-1] > i-1 we know A[i-1] >= i. Maximum k = i;

So, we need to find out the first element smaller than or equal to i.

bool lt(int a, int b){return a>b;}

int findPivotCount(vector<int>& A)
{
    int len = A.size();
    if(0 == len) return 0;
    sort(A.begin(), A.end(), lt);
    for(int i=0;i<len;i++)
    {
        if(A[i] <= i) return i;
    }
    return len;
}

This solution will take O(nlogn). Let's give an O(n) solution.
Note that fact the result is at largest n, which is the length the array. Let b[i] be the count of elements with value i. sum(b[j]), i<=j<=n will be the count of elements whose values are larger than or equal to i.

int findPivotCount(vector<int>& A)
{
    int len = A.size();
    vector<int> b(len+1, 0);
    for(int i=0;i<len;i++)
    {
        if(A[i]<0) continue;
        int t = A[i]>len?len:A[i];
        b[t]++;
    }
    int sum = 0;
    for(int i=len;i>=0;i--)
    {
        sum += b[i];
        if(sum >= i) return i;
    }
    return 0;
}