LeetCode 初级算法之数组(上),看看你都学会了吗?
theme: juejin highlight: xcode
本文正在参加「金石计划 . 瓜分6万现金大奖」
前言:最近自己也开始系统的刷面试题了,算法是过不去的坎,希望自己能够坚持下去✊,同行的朋友们共勉。
题一:删除排序数组中的重复项
给你一个 升序排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
注意:不要使用额外的空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1:
输入:nums = [1,1,2]
输出:2, nums = [1,2,_]
解题思路:双指针
因为有约束条件,不可以使用额外空间,所以这里不考虑使用字典来去重;在这里可以使用双指针
,即 前指针
和 后指针
。
我们可以通过遍历数组,判断两个相邻的指针所指向的值是否相等,如果不相等,则说明两者不重复,将后指针的值插入到维护的下标下。如果相等,则不处理。
需要注意下标越界;
时间复杂度:O(n)\ 空间复杂度:O(1)
代码
Swift
func removeDuplicates(_ nums: inout [Int]) -> Int {
var startIndex = 0
for index in 0..<nums.count-1 {
if nums[index] != nums[index+1] {
startIndex+=1
nums[startIndex] = nums[index+1]
}
}
return startIndex+1
}
题二:翻转数组
给你一个数组,将数组中的元素向右轮转
k
个位置,其中k
是非负数。
输入一: ``` 输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4]
解释: 向右轮转 1 步: [7, 1, 2, 3, 4, 5, 6] 向右轮转 2 步: [6, 7, 1, 2, 3, 4, 5] 向右轮转 3 步: [5, 6, 7, 1, 2, 3, 4] ```
输入二:
输入:nums = [-1,-100,3,99], k = 2
输出:[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
解题思路:环形翻转、多次翻转、临时数组
解法一:环形翻转
以输入一为例: 1,2,3,4,5,6,7, k = 3
1 ——> 4, 4 ——> 7, 7 ——> 3, 3 ——> 6, 6 ——> 2, 2 ——> 5, 5 ——> 1,
输出:5,6,7,1,2,3,4
环形翻转的思路就是以上流程的演变。
将第0
位的值向右移动k
,然后将k
位置下的值移动到k + k
位置下,依次循环替换; \
在替换前需要缓存后者的值,替换完之后,将操作的指针后移;
另外需要考虑到 nums.length%k=0
的情况,被整除了会在几个元素中循环;(被整除的情况下,仅在个别元素中来回翻转,并不能形成一个大环)
以输入二为例: -1, -100, 3, 99, k = 2
-1 ——> 3, 3 ——> -1, -1 ——> 3, ...
输出:-1, -100, -1, 99
如果这里没考虑到nums.length%k=0
被整除的情况,就会出现以上的问题,在这里可以添加一个字典来缓存已经访问过的下标。如果出现命中缓存的情况,就从它的下一位开始。
综合以上的情况可以得出以下的思路,
代码
```swift func rotate(_ nums: inout [Int], _ k: Int) { var index = 0; var last = nums[index] // 前指针 用来赋值 var temp = nums[index] // 后指针 用来先保存下一个位置的值 var visiter = Int:Int // 访问过的下标集合 for _ in 0..<nums.count { // 移动下标计算 // index = index+k < nums.count ? index+k : (index+k)%nums.count => index = (index+k)%nums.count index = (index+k)%nums.count // 如果访问过,需要打破小环; if visiter[index] != nil { while visiter[index] != nil { index+=1; } last = nums[index] index = (index+k)%nums.count }
/// 常规操作: /// 先把后指针的值缓存, /// 再把前指针的值插入后指针位置, /// 再把缓存值返回给前指针,保证在下一轮替换前,index和前指针的值同步; temp = nums[index] nums[index] = last last = temp visiter[index] = index; } } ```
解法二:多次翻转
这里需要通过三次翻转,即可完成;
第一次:因为数组元素往右移动,所以肯定有元素会被移动到左边,这里先做一次整体翻转;\
第二次:通过移动值与长度值取余(k%n
),得出分界线,前翻转范围(0,(k%n)-1)
,在此范围内的元素翻转;\
第三次:最后将后翻转范围(k%n,n-1)
内的元素进行翻转;
代码
```swift func rotate(_ nums: inout [Int], _ k: Int) { let index = k%nums.count reverse(&nums, 0, nums.count-1) reverse(&nums, 0, index-1) reverse(&nums, index, nums.count-1) }
func reverse(_ nums: inout [Int], _ start: Int, _ end: Int) { var start = start var end = end while (start < end) { nums.swapAt(start, end) start += 1 end -= 1 } } ```
解法三:临时数组
使用一个临时数组存放原数组的值,然后再把临时数组的值赋值给原数组,不过这里还需要将每个元素往后移动k位。下标可以通过(i + k) % length
来计算;
题三:存在重复元素
给你一个整数数组
nums
。如果任一值在数组中出现 至少两次 ,返回true
;如果数组中每个元素互不相同,返回false
。
示例 1:
输入: nums = [1,2,3,1]
输出: true
示例 2:
输入: nums = [1,2,3,4]
输出: false
解题思路:排序法、集合法
第一种思路: 如果给你的是一个排序后的数组,判断它是否存在重复元素是不是很简单,使用双指针判断就可以了。
第二种思路: 如果条件允许,使用键值(key-value)的集合去缓存数组中的元素,使用元素值当作key,如果下次被命中,同样可以知道数组存在重复元素。
第三种思路:
如果你知道无序集合set
的话,你就知道无序集合不存在重复元素,那么这是不是也是一种思路呢?😏
二和三的思路都是借助集合的形式,只是方式上有些不同。
解法一:排序法
将一个数组排序后,通过双指针遍历数组,若两个相邻的指针(i,i+1
)数值相同,则存在重复元素,返回true,如果不重复,则指针同时向后移动;
如果遍历完也没有重复,返回false。
代码
swift
func containsDuplicate2(_ nums: [Int]) -> Bool {
var newNums = nums
newNums.sort()
for i in 0..<nums.count-1 {
if newNums[i] == newNums[i+1] {
return true
}
}
return false
}
解法二:集合法
利用字典的特性,可以将数组元素的值作为字典的key。当你发现key键下已经存在时,证明已经存在重复数据。
代码
swift
func containsDuplicate(_ nums: [Int]) -> Bool {
var numDict = [Int: Int]()
for num in nums {
if numDict[num] == nil {
numDict[num] = num
} else {
return false
}
}
return true
}
题四:只出现一次的数字
给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。
示例 1 : ``` 输入:nums = [2,2,1] 输出:1
```
示例 2 :
输入:nums = [4,1,2,1,2]
输出:4
解题思路:位运算
如果说你只看标题,没有注意下面的要求,那么你可能会觉得就这
。。。
找出不重复的元素并不难,即便是使用线性时间复杂度一样也有很多方法可以解决。但是难在该算法只使用常量额外空间。也就是我们不用借助外部空间去实现。
话说回来,有什么好的解题思路呢,答案就是位运算。通过使用位运算中的异或操作符即可。
异或:
数学符号:⊕\ 编程符号:^
任何数和它自己异或都是0, a ⊕ a = 0\ 任何数和0异或都是它自己, a ⊕ 0 = a\ 异或运算满足交换律和结合律, a ⊕ b ⊕ a = a ⊕ a ⊕ b = 0 ⊕ b = b
代码
swift
func singleNumber(_ nums: [Int]) -> Int {
var result = 0
for num in nums {
result ^= num
}
return result
}
- LeetCode 初级算法之数组(上),看看你都学会了吗?
- LeetCode 初级算法之链表,看看你都学会了吗?
- LeetCode 初级算法之字符串(上),看看你都学会了吗?
- 纯代码布局,也可以一样的简洁
- UIStackView之一问一答
- 使用UIStackView来简化iOS的界面布局
- 夏天来了,iOS开发者们该如何减少App耗电?(上)
- 夏天来了,App开发者们如何看待手机发烫问题?
- 聊聊iOS中UITableView复用的那些事
- 曾经经典的微信打飞机游戏还有人记得吗?
- iOS 原生渲染与 Flutter 有什么区别 (上)
- 了解 Mach-O文件
- CocoaPods中podsepc文件设置详解
- iOS 原生渲染与 Flutter 有什么区别 (下)
- 简单了解 iOS CVPixelBuffer (上)
- 谈谈 iOS 包瘦身方案
- 播放器重构的探索之路
- 如何使用CocoaPods制作私有库
- iOS 组件化方案