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.
Given an integer array, find if there exists an integer p such that the number of integers strictly greater than p in the array is exactly p.
If such an integer exists, return 1. Otherwise, return -1.
If we sort the array, the number of elements greater than a given value is easy to compute as the number of elements to its right. We need to be careful with duplicates: only consider a value if it is the last occurrence of that value in the sorted array.
classSolution {
public:int solve(vector<int>&A) {
sort(A.begin(), A.end());
int n = A.size();
for (int i =0; i < n -1; ++i) {
if (A[i] == A[i+1]) continue;
if (A[i] == n - i -1) return1;
}
if (A[n-1] ==0) return1;
return-1;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
classSolution {
publicintsolve(int[] A) {
Arrays.sort(A);
int n = A.length;
for (int i = 0; i < n - 1; i++) {
if (A[i]== A[i+1]) continue;
if (A[i]== n - i - 1) return 1;
}
if (A[n-1]== 0) return 1;
return-1;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
from typing import List
classSolution:
defsolve(self, A: List[int]) -> int:
A.sort()
n = len(A)
for i in range(n -1):
if A[i] == A[i+1]:
continueif A[i] == n - i -1:
return1if A[-1] ==0:
return1return-1