LC 2733.Neither Minimum nor Maximum

题目描述

这是 LeetCode 上的 2733. 既不是最小值也不是最大值 ，难度为简单。

给你一个整数数组 nums ，数组由 不同正整数 组成，请你找出并返回数组中 任一 既不是 最小值 也不是 最大值 的数字，如果不存在这样的数字，返回 -1 。

返回所选整数。

示例 1：

输入：nums = [3,2,1,4]
输出：2
解释：在这个示例中，最小值是 1 ，最大值是 4 。因此，2 或 3 都是有效答案。

示例 2：

输入：nums = [1,2]
输出：-1
解释：由于不存在既不是最大值也不是最小值的数字，我们无法选出满足题目给定条件的数字。因此，不存在答案，返回 -1 。

示例 3：

输入：nums = [2,1,3]
输出：2
解释：2 既不是最小值，也不是最大值，这个示例只有这一个有效答案。 

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• nums 中的所有数字互不相同

解答

方法一：原地交换

由于数组中的整数都不相同，所以可以把最小值放在第一个位置，最大值放在最后一个位置，最后取第二个位置的值即可。如果题目中的整数允许存在相同的数，沿用相同的思路，使用两个指针，分别指向第一个位置和最后一个位置，遇到相同的数就移动指针，如果遇到不同的数就将指针返回起点。

class Solution {
    public int findNonMinOrMax(int[] nums) {
        if (nums.length < 3) {
            return -1;
        }
        for (int i = 0; i < nums.length; ++i) {
            int tmp = nums[i];
            if (nums[i] < nums[0]) {
                nums[i] = nums[0];
                nums[0] = tmp;
            }
            if (nums[i] > nums[nums.length - 1]) {
                nums[i] = nums[nums.length - 1];
                nums[nums.length - 1] = tmp;
            }
        }
        return nums[1];
    }
}

• 时间复杂度：\(O(n)\)，其中 n 是数组 nums 的长度。

• 空间复杂度：\(O(1)\)。

方法二：前三个元素排序

@Source: 题解来源

由于既不是最大值也不是最小值，并且整数互不相同，所以可以直接排序前三个数，取中间的数。

class Solution {
    public int findNonMinOrMax(int[] nums) {
        if (nums.length < 3) {
            return -1;
        }
        Arrays.sort(nums, 0, 3); // 只对前三个数排序
        return nums[1];
    }
}

• 时间复杂度：\(O(1)\)。

• 空间复杂度：\(O(1)\)。

每题一图