1608.特殊数组的特征值

LeetCode LeetCode 数组排序二分查找

发布时间 : 2000-01-11 06:00

字数:1.7k 阅读 :

评论:

1608.特殊数组的特征值

1608.特殊数组的特征值

1608.1 题目

给你一个非负整数数组 nums。如果存在一个数 x，使得 nums 中恰好有 x 个元素大于或者等于 x，那么就称 nums 是一个特殊数组，而 x 是该数组的特征值。

注意：x 不必是 nums 的中的元素。

如果数组 nums 是一个特殊数组，请返回它的特征值 x。否则，返回 -1。可以证明的是，如果 nums 是特殊数组，那么其特征值 x 是唯一的。

示例 1：

输入：nums = [3,5]
输出：2
解释：有 2 个元素（3 和 5）大于或等于 2。

示例 2：

输入：nums = [0,0]
输出：-1
解释：没有满足题目要求的特殊数组，故而也不存在特征值 x。
如果 x = 0，应该有 0 个元素 >= x，但实际有 2 个。
如果 x = 1，应该有 1 个元素 >= x，但实际有 0 个。
如果 x = 2，应该有 2 个元素 >= x，但实际有 0 个。
x 不能取更大的值，因为 nums 中只有两个元素。

示例 3：

输入：nums = [0,4,3,0,4]
输出：3
解释：有 3 个元素大于或等于 3。

示例 4：

输入：nums = [3,6,7,7,0]
输出：-1

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 1000

1608.2 题解

暴力枚举法

// 方法一：暴力枚举法
// 排序后双循环遍历统计
static int SpecialArray1(int[] nums)
{
    // 将数组排序
    Array.Sort(nums);

    // 获取数组长度
    int numsLength = nums.Length;

    // 枚举特征值 x，x 的范围为 [0, n]
    for (int x = 0; x <= numsLength; x++)
    {
        // 记录大于或等于 x 的元素个数
        int count = 0;

        // 遍历数组，统计大于或等于 x 的元素个数
        for (int i = 0; i < numsLength; i++)
        {
            if (nums[i] >= x)
                count++;
        }

        // 如果大于或等于 x 的元素个数等于 x，则返回 x
        if (count == x)
            return x;
    }

    // 如果不存在满足条件的 x，则返回 -1
    return -1;
}

降序排序遍历判断

// 方法二：降序排序遍历判断
// 如果数组中前 i 个元素中的最小值大于等于 i，
// 且数组中的第 i 个元素小于 i（或者 i 等于数组的长度）
// 则返回 i 作为特征值
static int SpecialArray2(int[] nums)
{
    // 将数组排序
    Array.Sort(nums);

    // 反转数组，使其按降序排列
    Array.Reverse(nums);

    // 枚举特征值 i，i 的范围为 [1, 数组长度]
    for (int i = 1; i <= nums.Length; i++)
    {
        // 如果数组中前 i 个元素中的最小值大于等于 i，
        // 且数组中的第 i 个元素小于 i（或者 i 等于数组的长度）
        // 则返回 i 作为特征值
        if (nums[i - 1] >= i && (i == nums.Length || nums[i] < i))
        {
            return i;
        }
    }

    // 如果不存在满足条件的特征值，则返回 -1
    return -1;
}

1608.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

        // 给你一个非负整数数组 nums 。如果存在一个数 x ，使得 nums 中恰好有 x 个元素 大于或者等于 x ，
        // 那么就称 nums 是一个 特殊数组 ，而 x 是该数组的 特征值 。
        // 注意： x 不必 是 nums 的中的元素。
        // 如果数组 nums 是一个 特殊数组 ，请返回它的特征值 x 。否则，返回 -1 。
        // 可以证明的是，如果 nums 是特殊数组，那么其特征值 x 是 唯一的 。

        // 示例 1：
        // 输入：nums = [3,5]
        // 输出：2
        // 解释：有 2 个元素（3 和 5）大于或等于 2 。

        // 示例 2：
        // 输入：nums = [0,0]
        // 输出：-1
        // 解释：没有满足题目要求的特殊数组，故而也不存在特征值 x 。
        // 如果 x = 0，应该有 0 个元素 >= x，但实际有 2 个。
        // 如果 x = 1，应该有 1 个元素 >= x，但实际有 0 个。
        // 如果 x = 2，应该有 2 个元素 >= x，但实际有 0 个。
        // x 不能取更大的值，因为 nums 中只有两个元素。

        // 示例 3：
        // 输入：nums = [0,4,3,0,4]
        // 输出：3
        // 解释：有 3 个元素大于或等于 3 。

        // 示例 4：
        // 输入：nums = [3,6,7,7,0]
        // 输出：-1

        // 提示：
        // 1 <= nums.length <= 100
        // 0 <= nums[i] <= 1000

        #endregion

        #region 测试

        // 示例 1
        int[] nums1 = { 3, 5 };
        int result1_1 = SpecialArray1(nums1);
        Console.WriteLine($"示例1 方法1 输出：{result1_1}");
        int result1_2 = SpecialArray2(nums1);
        Console.WriteLine($"示例1 方法2 输出：{result1_2}");

        // 示例 2
        int[] nums2 = { 0, 0 };
        int result2_1 = SpecialArray1(nums2);
        Console.WriteLine($"示例2 方法1 输出：{result2_1}");
        int result2_2 = SpecialArray2(nums2);
        Console.WriteLine($"示例2 方法2 输出：{result2_2}");

        // 示例 3
        int[] nums3 = { 0, 4, 3, 0, 4 };
        int result3_1 = SpecialArray1(nums3);
        Console.WriteLine($"示例3 方法1 输出：{result3_1}");
        int result3_2 = SpecialArray2(nums3);
        Console.WriteLine($"示例3 方法2 输出：{result3_2}");

        // 示例 4
        int[] nums4 = { 3, 6, 7, 7, 0 };
        int result4_1 = SpecialArray1(nums4);
        Console.WriteLine($"示例4 方法1 输出：{result4_1}");
        int result4_2 = SpecialArray2(nums4);
        Console.WriteLine($"示例4 方法2 输出：{result4_2}");

        #endregion
    }

    #region 答案

    // 方法一：暴力枚举法
    // 排序后双循环遍历统计
    static int SpecialArray1(int[] nums)
    {
        // 将数组排序
        Array.Sort(nums);

        // 获取数组长度
        int numsLength = nums.Length;

        // 枚举特征值 x，x 的范围为 [0, n]
        for (int x = 0; x <= numsLength; x++)
        {
            // 记录大于或等于 x 的元素个数
            int count = 0;

            // 遍历数组，统计大于或等于 x 的元素个数
            for (int i = 0; i < numsLength; i++)
            {
                if (nums[i] >= x)
                    count++;
            }

            // 如果大于或等于 x 的元素个数等于 x，则返回 x
            if (count == x)
                return x;
        }

        // 如果不存在满足条件的 x，则返回 -1
        return -1;
    }

    // 方法二：降序排序遍历判断
    // 如果数组中前 i 个元素中的最小值大于等于 i，
    // 且数组中的第 i 个元素小于 i（或者 i 等于数组的长度）
    // 则返回 i 作为特征值
    static int SpecialArray2(int[] nums)
    {
        // 将数组排序
        Array.Sort(nums);

        // 反转数组，使其按降序排列
        Array.Reverse(nums);

        // 枚举特征值 i，i 的范围为 [1, 数组长度]
        for (int i = 1; i <= nums.Length; i++)
        {
            // 如果数组中前 i 个元素中的最小值大于等于 i，
            // 且数组中的第 i 个元素小于 i（或者 i 等于数组的长度）
            // 则返回 i 作为特征值
            if (nums[i - 1] >= i && (i == nums.Length || nums[i] < i))
            {
                return i;
            }
        }

        // 如果不存在满足条件的特征值，则返回 -1
        return -1;
    }

    #endregion
}

1608.4 运行结果

示例1 方法2 输出：2
示例2 方法1 输出：-1
示例2 方法2 输出：-1
示例3 方法1 输出：3
示例3 方法2 输出：3
示例4 方法1 输出：-1
示例4 方法2 输出：-1

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com