iOS object-C 解答算法:找到所有数组中消失的数字(leetCode-448)
找到所有数组中消失的数字(leetCode-448)
题目如下图:(也可以到leetCode上看完整题目,题号448)
光看题看可能有点难以理解,我们结合示例1来理解一下这道题.
有8个整数的数组 nums = [4,3,2,7,8,2,3,1], 求在闭区间[1,8]范围内(即1,2,3,4,5,6,7,8)的数字,哪几个没有出现在数组 nums 中.
我们很容易一看就看出,5和6没有出现在数组nums中.
还是拿示例1来说,如果可以用新建一个数组newNums = [1,2,3,4,5,6,7,8] 与 原数组nums = [4,3,2,7,8,2,3,1] 比较,立马可以找到缺少了元素5和6,但是题目要求不得使用额外空间.所以只能在原数组上操作.
解法一:
我们先来说一下常规解法(就是可以使用额外空间的解法). 遍历nums数组,把遍历到的元素一一在newNums数组里删除,剩下没删除的元素就是nunms没有的.
代码如下:
- (void)viewDidLoad
{
[super viewDidLoad];
NSMutableArray * originalArray = [[NSMutableArray alloc]initWithObjects:@"4",@"3",@"2",@"7",@"8",@"2",@"3",@"1", nil];
NSMutableArray * newArray = [[NSMutableArray alloc]init];
for (int i = 1; i < originalArray.count + 1; i ++)
{
[newArray addObject:[NSString stringWithFormat:@"%d",i]];
}
NSMutableArray * array2 = [self missNum:originalArray NewArray:newArray];
NSLog(@"array2==%@",array2);
}
- (NSMutableArray *)missNum:(NSMutableArray *)originalArray NewArray:(NSMutableArray *)newArray
{
for (int i = 0 ; i < originalArray.count; i ++)
{
NSString * oValue = originalArray[i];
[newArray removeObject:oValue];
}
return newArray;
}以上就是我们通常想到的常规解法,时间复杂度为O(n^2),空间复杂度为O(n).
因为要创建newArray,所以多了一个O(n)的空间. 我们再按照题目的要求,时间复杂度为O(n),不额外增加空间的解法.
解法二:
我们可以把 数组nums = [4,3,2,7,8,2,3,1] 看做是 数组newNums = [1,2,3,4,5,6,7,8],减去几个数,再增加几个相同的数(例如这里增加了2和3),再打乱它们的排列组合. 注意:nums和newNums的元素个数(就是count一定是相等的,这是题目隐含的意思).
所以在nums 里的index=0的元素4, 它原来的index应该为3. 我们就按照这个逻辑,把nums里所有元素的的原index都找到,那么剩下的没有找到的index,就是没有出现在nums 里的元素.
思路如下:
nums元素 4---->index = 3
nums元素 3---->index = 2
nums元素 2---->index = 1
nums元素 7---->index = 6
nums元素 8---->index = 7
nums元素 2---->index = 1
nums元素 3---->index = 2
nums元素 1---->index = 0
通过上面列出的思路,我们可以看到,index=4和index=5 没有出现,所以没有出现的数字为 5 和 6.
因为不能额外增加空间,所以我们不能新创建一个数组和存放index.那么我们只能使用标记法-->在原数组标记.
标记的方法有很多种,例如可以在数组前加个减号(-)标记, 也可以每个元素加上n标记(例如4+8),也可以使用符号标志(例如*,但是这道题是数字,明显不能用这个方法).
我们这里就使用减号标志号了
nums元素 4 ---> index = 3 ,在数组nums index=3的位置加个减号:nums = [4,3,2,-7,8,2,3,1];
nums元素 3 ---> index = 2 ,在数组nums index=2的位置加个减号:nums = [4,3,-2,-7,8,2,3,1];
nums元素 2 ---> index = 1 ,在数组nums index=1的位置加个减号:nums = [4,-3,-2,-7,8,2,3,1];
我们下一步按理说是要取元素7的,但是nums里7 已经变成-7了,所以我们为了不受标记影响,我们每次都取元素的绝对值(object-c取数字绝对值的方法为abs())
nums元素 7 ---> index = 6 ,在数组nums index=6的位置加个减号:nums = [4,-3,-2,-7,8,2,-3,1];
nums元素 8 ---> index = 7 ,在数组nums index=7的位置加个减号:nums = [4,-3,-2,-7,8,2,-3,-1];
下一步的元素2.index=1 的位置已经标记了减号,所以我么标记之前先判断待标记的位置是否为负数,如果为负数,则无需重复标记
nums元素 2 ---> index = 1 ,无需重复标记
nums元素 3 ---> index = 2 ,无需重复标记
nums元素 1 ---> index = 0,在数组nums index=0的位置加个减号:nums = [-4,-3,-2,-7,8,2,-3,-1];
经过一个for循环的标记,我们就找出数组里为正数数的index,即得到没有出现的数字
代码如下:
- (NSMutableArray *)missNum2:(NSMutableArray *)originalArray
{
for (int i = 0 ; i < originalArray.count; i ++)
{
//1.取值要取绝对值 abs()
int value = abs([originalArray[i] intValue]);
//2.获得元素的index
int index = value - 1;
//3.标记index
//3.1.标记之前要判断index的元素是否为负数,如果为负数,则说明已经标记过了,无需标记
if (originalArray[index] > 0)
{
originalArray[index] = [NSString stringWithFormat:@"-%@",originalArray[index]];
}
NSLog(@"originalArray==%@",originalArray);
}
NSMutableArray * newArray = [[NSMutableArray alloc]init];
for (int i = 1; i < originalArray.count + 1; i ++)
{
[newArray addObject:[NSString stringWithFormat:@"%d",i]];
}
return newArray;
}以上代码的时间复杂度为O(n),空间复杂度也为O(n)
原文地址：https://blog.csdn.net/wyz670083956/article/details/140535083
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！