5940 从数组中移除最大值和最小值

发表于

这是我参与11月更文挑战的第28天，活动详情查看：2021最后一次更文挑战

  1. 从数组中移除最大值和最小值

给你一个下标从 0 开始的数组 nums ，数组由若干 互不相同 的整数组成。

nums 中有一个值最小的元素和一个值最大的元素。分别称为 最小值 和 最大值 。你的目标是从数组中移除这两个元素。

一次 删除 操作定义为从数组的 前面 移除一个元素或从数组的 后面 移除一个元素。

返回将数组中最小值和最大值 都 移除需要的最小删除次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
ini复制代码示例 1：

输入：nums = [2,10,7,5,4,1,8,6]
输出：5
解释：
数组中的最小元素是 nums[5] ，值为 1 。
数组中的最大元素是 nums[1] ，值为 10 。
将最大值和最小值都移除需要从数组前面移除 2 个元素，从数组后面移除 3 个元素。
结果是 2 + 3 = 5 ，这是所有可能情况中的最小删除次数。

示例 2：

输入：nums = [0,-4,19,1,8,-2,-3,5]
输出：3
解释：
数组中的最小元素是 nums[1] ，值为 -4 。
数组中的最大元素是 nums[2] ，值为 19 。
将最大值和最小值都移除需要从数组前面移除 3 个元素。
结果是 3 ，这是所有可能情况中的最小删除次数。 

示例 3：

输入：nums = [101]
输出：1
解释：
数组中只有这一个元素，那么它既是数组中的最小值又是数组中的最大值。
移除它只需要 1 次删除操作。

提示：

  • 1 <= nums.length <= 10510^5105
  • −105-10^5−105 <= nums[i] <= 10510^5105
  • nums 中的整数 互不相同

解题思路

  1. 统计最大值和最小值所在的下标，因为在这题中，哪个是最大值，哪个是最小值对题目并不影响，因此我们只需要知道左边极值的下标和右边极值的下标即可。
  2. 共有三种删除方法
  • 从数组的 前面 移除元素，直到把右边的极值移除
  • 从数组的 后面 移除元素，直到把左边的极值移除
  • 从数组的两边一齐移除元素，直到把左边和右边的极值移除

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
cpp复制代码class Solution {
public:
    int minimumDeletions(vector<int>& nums) {

        int max_i(0),min_i(0),n=nums.size();
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i]>nums[max_i])
                max_i=i;
            if (nums[i]<nums[min_i])
                min_i=i;
        }
        int l=min(max_i,min_i),r=max(max_i,min_i);

        return min(l+1+n-r,min(r+1,n-l));

    }
};

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%