Noble Integer

Given an integer array, find if an integer p exists in the array such that the number of integers greater than p in the array equals to p
If such an integer is found return 1 else return -1.

https://www.interviewbit.com/problems/noble-integer/

思路

如果array是sorted，那么我们就能通过index直接确定比当前数大的number的个数。
注意有两个corner case
  • 如果有duplicate number，我们需要以这个数在sorted array中的最后一次出现的index为基准
  • 如果array中最大的数是0，那么我们也需要返回1

Solution

Time: O(nlogn)
Space: O(1)

public class Solution {
    public int solve(ArrayList<Integer> A) {
        Collections.sort(A);
        for (int i = 1; i < A.size(); i ++) {
            int curr = A.get(i);
            int prev = A.get(i - 1);
            if (prev != curr) {
                int number_of_int_greater_than_prev = A.size() - i;
                if (prev == number_of_int_greater_than_prev) {
                    return 1;
                }
            }
        }
        if (A.get(A.size() - 1) == 0) return 1; 
        return -1;
    }
}