寻找贵族整数（Noble Integers）Java解法：部分测试用例未通过

你的代码存在三个核心问题，导致无法通过所有测试用例：

• 逻辑匹配错误：你将降序数组的索引i与数组元素newarr[i]直接比较，这不符合题目要求。题目需要的是「大于p的元素个数等于p」，而i仅代表前i+1个元素大于等于newarr[i]，并非大于newarr[i]的元素数量。
• 未覆盖非数组元素的p：p可以是数组中不存在的整数，比如数组[1,3,4]中，p=2时大于2的元素有2个，符合条件，但你的代码不会检查这种情况。
• 重复元素处理失效：当数组存在重复元素时，会出现误判。比如数组[2,2,2]，你的代码会因为newarr[2] == 2返回1，但实际上大于2的元素个数为0，不等于2。

修正后的代码 #

import java.util.Arrays;

public class Solution {
    public int solve(int[] A) {
        Arrays.sort(A);
        int n = A.length;
        
        for (int i = 0; i < n; i++) {
            // 跳过重复元素，避免重复计算与误判
            if (i < n - 1 && A[i] == A[i + 1]) {
                continue;
            }
            // 计算大于当前元素A[i]的元素个数
            int count = n - i - 1;
            // 情况1：p等于数组中的元素A[i]，判断数量是否匹配
            if (count == A[i]) {
                return 1;
            }
            // 情况2：p落在当前元素与下一个元素之间，判断count是否处于该区间
            if (i < n - 1 && count > A[i] && count < A[i + 1]) {
                return 1;
            }
        }
        
        return -1;
    }
}

逻辑解释 #

1. 排序数组：将数组升序排序后，可快速计算出大于任意元素的元素数量。
2. 跳过重复元素：避免对相同元素重复计算，同时防止重复元素导致的逻辑误判。
3. 双场景检查：
   • 场景1：p是数组中的元素，此时大于p的元素个数为n - i - 1，直接判断该数量是否等于p。
   • 场景2：p不是数组中的元素，此时p必然落在两个相邻元素之间，若大于p的元素个数恰好等于p，且p处于对应区间内，则符合条件。

内容的提问来源于stack exchange，提问作者Swarnim Anand