LeetCode 2784. 检查数组是否是好的【原地修改数组】简单-平芜编程栈

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你一个整数数组nums，如果它是数组base[n]的一个排列，我们称它是个好数组。

base[n] = [1, 2, ..., n - 1, n, n]（换句话说，它是一个长度为n + 1且包含1到n - 1恰好各一次，包含n两次的一个数组）。比方说，base[1] = [1, 1]，base[3] = [1, 2, 3, 3]。

如果数组是一个好数组，请你返回true，否则返回false。

注意：数组的排列是这些数字按任意顺序排布后重新得到的数组。

示例 1：

输入：nums=[2,1,3]输出：false解释：因为数组的最大元素是3，唯一可以构成这个数组的 base[n]对应的 n=3。但是 base[3]有4个元素，但数组 nums 只有3个元素，所以无法得到 base[3]=[1,2,3,3]的排列，所以答案为false。

示例 2：

输入：nums=[1,3,3,2]输出：true解释：因为数组的最大元素是3，唯一可以构成这个数组的 base[n]对应的 n=3，可以看出数组是 base[3]=[1,2,3,3]的一个排列（交换 nums 中第二个和第四个元素）。所以答案为true。

示例 3：

输入：nums=[1,1]输出：true解释：因为数组的最大元素是1，唯一可以构成这个数组的 base[n]对应的 n=1，可以看出数组是 base[1]=[1,1]的一个排列。所以答案为true。

示例 4：

输入：nums=[3,4,4,1,2,1]输出：false解释：因为数组的最大元素是4，唯一可以构成这个数组的 base[n]对应的 n=4。但是 base[n]有5个元素而 nums 有6个元素。所以答案为false。

提示：

1 <= nums.length <= 100
1 <= num[i] <= 200

方法一辅助数组

遍历n u m s numsnums，同时用一个数组c n t cntcnt统计每个元素的出现次数。

设n nn是n u m s numsnums的长度减一。设x = n u m s [ i ] x = nums[i]x=nums[i]。分类讨论：

如果x > n x > nx>n，不满足要求，返回f a l s e falsefalse。注意题目保证x ≥ 1 x \ge 1x≥1，无需判断x ≤ 0 x \le 0x≤0的情况。
如果x = = n x == nx==n且x xx出现次数大于2 22，返回f a l s e falsefalse。
如果x < n x < nx<n且x xx出现次数大于1 11，返回f a l s e falsefalse。

如果没有出现上述情况，返回t r u e truetrue。

classSolution{publicbooleanisGood(int[]nums){intn=nums.length-1;int[]cnt=newint[n+1];for(intx:nums){if(x>n||x==n&&cnt[x]>1||// cnt[x] 加一之前 > 1，加一之后 > 2x<n&&cnt[x]>0){// cnt[x] 加一之前 > 0，加一之后 > 1returnfalse;}cnt[x]++;}returntrue;}}

classSolution{public:boolisGood(vector<int>&nums){intn=nums.size()-1;vector<int>cnt(n+1);for(intx:nums){if(x>n||x==n&&cnt[x]>1||// cnt[x] 加一之前 > 1，加一之后 > 2x<n&&cnt[x]>0){// cnt[x] 加一之前 > 0，加一之后 > 1returnfalse;}cnt[x]++;}returntrue;}};

classSolution:defisGood(self,nums:List[int])->bool:n=len(nums)-1cnt=[0]*(n+1)forxinnums:if(x>norx==nandcnt[x]>1or# cnt[x] 加一之前 > 1，加一之后 > 2x<nandcnt[x]>0):# cnt[x] 加一之前 > 0，加一之后 > 1returnFalsecnt[x]+=1returnTrue

funcisGood(nums[]int)bool{n:=len(nums)-1cnt:=make([]int,n+1)for_,x:=rangenums{ifx>n||x==n&&cnt[x]>1||// cnt[x] 加一之前 > 1，加一之后 > 2x<n&&cnt[x]>0{// cnt[x] 加一之前 > 0，加一之后 > 1returnfalse}cnt[x]++}returntrue}

复杂度分析：

时间复杂度：O ( n ) O(n)O(n)，其中n nn是n u m s numsnums的长度。
空间复杂度：O ( n ) O(n)O(n)。

方法二把n u m s numsnums当作辅助数组

由于n u m s numsnums中的数都是正整数，我们可在首次遇到元素x xx时，把n u m s [ x ] nums[x]nums[x]改为− n u m s [ x ] -nums[x]−nums[x]，这样再次遇到∣ x ∣ |x|∣x∣时，就能通过n u m s [ ∣ x ∣ ] < 0 nums[ |x| ] < 0nums[∣x∣]<0得知n u m s numsnums中至少有两个∣ x ∣ |x|∣x∣。

对于n nn，我们要判断n nn是否出现超过两次，可以单独用一个变量c n t N cntNcntN统计n nn的出现次数。

classSolution{publicbooleanisGood(int[]nums){intn=nums.length-1;intcntN=0;for(intx:nums){x=Math.abs(x);if(x>n||x==n&&cntN>1||x<n&&nums[x]<0){// x 之前遇到过，现在又遇到了，所以 x 的出现次数至少是 2returnfalse;}if(x==n){cntN++;}else{nums[x]=-nums[x];// 标记 x 遇到过}}returntrue;}}

classSolution{public:boolisGood(vector<int>&nums){intn=nums.size()-1;intcnt_n=0;for(intx:nums){x=abs(x);if(x>n||x==n&&cnt_n>1||x<n&&nums[x]<0){// x 之前遇到过，现在又遇到了，所以 x 的出现次数至少是 2returnfalse;}if(x==n){cnt_n++;}else{nums[x]=-nums[x];// 标记 x 遇到过}}returntrue;}};

classSolution:defisGood(self,nums:List[int])->bool:n=len(nums)-1cnt_n=0forxinnums:x=abs(x)if(x>norx==nandcnt_n>1orx<nandnums[x]<0):# x 之前遇到过，现在又遇到了，所以 x 的出现次数至少是 2returnFalseifx==n:cnt_n+=1else:nums[x]=-nums[x]# 标记 x 遇到过returnTrue

funcisGood(nums[]int)bool{n:=len(nums)-1cntN:=0for_,x:=rangenums{x=abs(x)ifx>n||x==n&&cntN>1||x<n&&nums[x]<0{// x 之前遇到过，现在又遇到了，所以 x 的出现次数至少是 2returnfalse}ifx==n{cntN++}else{nums[x]=-nums[x]// 标记 x 遇到过}}returntrue}funcabs(xint)int{ifx<0{return-x}returnx}