介绍
一直想整理算法题目,由于之前一直用手写的方式，最后想想还是写成blog比较好，方便一些有需要的人，这篇blog会介绍array 分类里面的题目，尽量做到每一道题目，会长期持续更新
Array
写代码的人都知道array是啥，就是同一类型的一组数据，在算法中array起到了至关重要的角色。数组可以拓宽到排序，数据结构。 很多数据结构的底层就是拿array来实现
No.34. Search for a Range
Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4]. 给定一个排好序的数组，返回于target一样的最小下标和最大下标
暴力解法
找到第一个解，然后从第一个后面找到最后一个解
func SearchRange(nums []int, target int) []int {
firstIndex:=-1
for i:=0;i<len(nums);i++{
if nums[i]==target{
firstIndex = i
break
}
}
secondeIndex:=-1
if firstIndex==-1{
return []int{-1,-1}
}
for i:=firstIndex;i<len(nums);i++{
if nums[i]==target{
secondeIndex= i
}
}
return []int{firstIndex,secondeIndex}
}
- runtime: 22ms
- beats: 20%
- testcase: 83/83
- big O : n
由于数据量偏小 所以看不出多大区别 多试几次还能100%呢。 但是可以看出 这个算法的大O是N，题目要求要算法的大O 是logN.
解法1
这题目的重是在于排好序的，对于排好序的数组进行搜索，且大O是logN的 那么就可以考虑用 二分查找法。
- 找到最最前面的target，我们就要用二分查找取最前面的index
- 找到最最后面的target， 我们就要用二分查找最最后面的index
func binarySearchFirst(nums []int, target int) int{
targetIndex:=-1
start:=0
end:=len(nums)-1
for start<=end{
mid:=(start+end)>>1
if nums[mid]>=target{
end =mid-1
}else {
start =mid+1
}
if nums[mid]==target{
targetIndex=mid
}
}
return targetIndex
}
我们在判定条件中把大于等于归并到一起，这样做的原因就是每次，最后的结果会被第一个找到的值给覆盖
查找最后一位的话。只要把等于 跟小于归并到一起就行了
func binarySearchLast(nums []int, target int) int{
targetIndex:=-1
start:=0
end:=len(nums)-1
for start<=end{
mid:=(start+end)>>1
if nums[mid]<=target{
start =mid+1
}else {
end =mid-1
}
if nums[mid]==target{
targetIndex=mid
}
}
return targetIndex
}
所以代码最后是这样的：
func SearchRange(nums []int, target int) []int {
firstIndex:=binarySearchFirst(nums,target)
secondIndex:=binarySearchLast(nums,target)
return []int{firstIndex,secondIndex}
}
- runtime: 16ms
- beats: 80%
- testcase: 83/83
- big O : logN
No.75.Sort Colors
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note: You are not suppose to use the library’s sort function for this problem.
给定一个数组里面里面仅包含0，1，2。 给他们从小到大排序
暴力解法
任意选择一种排序，进行从小打到排序即可，什么冒泡，插入排序，堆排序等等。反正可以有排序功能就好了，啧啧
解法1
计算对应的所有个数然后重新进行排列
func SortColors(nums []int) {
colorNumber:=make([]int,3)
for _,color:=range nums{
colorNumber[color]++
}
startIndex:=0
endIndex:=-1
for i:=0;i<len(colorNumber);i++{
startIndex= endIndex+1
endIndex = startIndex+colorNumber[i]-1
for j:=startIndex;j<=endIndex;j++{
nums[j]=i
}
}
}
- runtime: 3ms
- beats: 4.03%
- testcase: 86/86
- big O : n=> 其实这里的时间复杂度应该是M(颜色总类)*N 由于颜色被定死在3 然后3n 最化简下是 N
解法2
看到数组里面的种类有限且种类不多的情况下可以考虑快速排序的
func SortColors(nums []int) {
zero:=-1 //前闭 和 后闭
two:= len(nums)
for i:=0;i<two;{
if nums[i]==1{
i++
}else if nums[i]==2{
two --
nums[two],nums[i] = nums[i],nums[two]
}else if nums[i]==0{
nums[i],nums[zero+1] = nums[zero+1],nums[i]
zero++
i++
}else{
return
}
}
}
- runtime: 3ms
- beats: 4.03%
- testcase: 86/86
- big O : nlogN
No.152. Maximum Product Subarray(也可以归并到DP题型中)
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.
给定一个数组，找出最大的乘积的子数组(划重点，子数组，乘积)
暴力解法
就针对于上面的解释很容易写出暴力解：就是把所有的子数组的乘积算出 然后找最大的那个
func maxProduct(nums []int) int {
max:=math.MinInt64
if len(nums)==1{
return nums[0]
}
for i:=0;i<len(nums);i++{
preResult:=nums[i]
if preResult>max{
max = preResult
}
for j:=i+1;j<len(nums);j++{
preResult*=nums[j]
if preResult>max{
max = preResult
}
}
}
return max
}
- runtime: 212ms
- beats: 5.56%
- testcase: 183/183
- big O : n^2
可以看出暴力解的大O 是n^2，明显是不够的
解法1
这道题用到了DP的思想，来看分析下情细节。
- 对于乘法来说，累乘的话，只要前面结果是正数的话，乘以一个正数那么会保持最大结果，
- 累乘的结果小于0 那么乘以一个负数也能产生最大值。
- 我们需要保留正数最大和负数最小。
- 如果当前数 比正数累乘和当前数的乘积 还要大 那么我们就要 抛弃之前的所有结果从新的起点开始计算，同理的如果比负数累乘还要小，那么也要新的开始。这种情况主要出现的情况是数组里面有0的情况。比如说[1,2,0,4,5] 很明显 1，2，0 我们需要抛弃从4 开始计算
思路理清楚了，代码也比较好出来了:
func maxProduct2(nums []int) int {
maxValue:=nums[0]
minValue:=nums[0]
ansValue:=nums[0]
for i:=1;i<len(nums);i++{
currentMax:= maxValue *nums[i]
currentMin := minValue *nums[i]
maxValue = max (max(currentMax,currentMin),nums[i])
minValue = min (min(currentMax,currentMin),nums[i])
ansValue = max(maxValue,ansValue)
}
return ansValue
}
func max(a,b int) int{
if a>b{
return a
}else{
return b
}
}
func min(a,b int) int{
if a<b{
return a
}else{
return b
}
}
由于golang 没有int的大小比较，所以需要自己手动写一个
- runtime: 6ms
- beats: 38.89%
- testcase: 183/183
- big O : n
No.153. Find Minimum in Rotated Sorted Array
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array. //先点首暖暖给自己
这道题嘛。就是给你一个从小到大排好序的数组，但是这个数组以某个下标为基点左右二边相互调换了。
暴力解法
//哦，最近有人问我，为什么要放暴力解法，那是因为 在实在想不出解法的暴力解他也是一种解嘛，不能看不起它嘛
暴力解的话就直接找到最小值呗
func findMin(nums []int) int {
min:=nums[0]
for i:=1;i<len(nums);i++{
if nums[i]<min{
min = nums[i]
}
}
return min
}
- runtime: 6ms
- beats: 9.52%
- testcase: 146 / 146
- big O : n
解法1
解法1呢稍微比暴力解好点，但是时间复杂度还是n，就给大家一个参考吧。由于这个数组是之前从小到大排好的，对不对。所以对调的话，就会是
就我把上面给的例子用图片表示出来了并且 对2个元素 进行了标示。 这二个元素有跟其他元素有不同的特点。犹豫之前的排序是从小到大的，所以 nums[i-1]< nums[i]< nums[i+1]
这二个元素表现为分界的前和分界的后。我们只需用到第二个元素 第二个元素的特点就是nums[i]< nums[i-1] && nums[i]< nums[i+1]
func findMin(nums []int) int {
for i:=1;i<len(nums)-1;i++{
if nums[i]<nums[i-1]&&nums[i]<nums[i+1]{
return nums[i]
}
}
if nums[0]>nums[len(nums)-1]{
return nums[len(nums)-1]
}else{
return nums[0]
}
}
- runtime: 6ms
- beats: 9.52%
- testcase: 146 / 146
- big O : n
时间复杂度还是n，但是这个方法不用每次都遍历所有元素。。嗯嗯嗯
解法2
emmmm, 之前提到过，如果元素是有顺序的排序，第一个想到的应该是二分查找法嘛。这道题可以用二分查找法嘛。答案是肯定的（弱弱点开这道题的分类也被归并在二分查找) 那么对于二分查找，我们无非就是要定义left，right 和判断条件了。 先来理清一个点，就是这个数组要么就是被换位了 要么就是没有换位。。我们想来找二个种情况的突破点。如果换位了那么就标示，较大的那一整块都被提前到最最前面了。
是不是可以发现一点，较大的最小值永远大于较小的最大值，也就是。也就是最前面的值永远大于最后的面值。。但是，如果仅从较小的那块数据看的话，是不是可以发现这块的最前面的值永远小于最后的值 那我们的临界点就是要找的 当 arr[left]< arr[right]的时候 那找到了临界点嘛，我们就要找中间点的情况，先看第一种情况
当我们的中间点大于最后右边的话，那么就说明 我们的目标在右边。 相反中间点小于的话那么就是 我们的目标点在左边 啊喂
func findMin(nums []int) int {
left :=0
right:= len(nums)-1
for left<right{
if nums[left]<nums[right]{
return nums[left]
}
mid:=(left+right)>>1
if nums[mid]<nums[right]{
right = mid
}else{
left = mid+1
}
}
return nums[left]
}
- runtime: 3 ms
- beats: 54.74%
- testcase: 146 / 146
- big O : logn
No.167. Two Sum II - Input array is sorted
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.
Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2
// 不知道为啥今天心情特别爆炸，也不是不好，就是感觉不舒服。发呆了一天，没啥都不想做。。 //不想看代码 不想看网课，不想上课。就打王者打了一天。。 直到阿博给我新任务的时候稍微调整过来一点 //博客还是要更新的，随意选了一道以前自己做过的题目
给定一个有序数组，和一个target值，取数组中的二个数，二个数的和要等于target。这道题中。告诉了只有一组解且存在解(返回的下标要从1开始哦)
暴力解法
暴力解嘛，求出所有解，然后返回对应的下标
func twoSum(numbers []int, target int) []int {
result:=make([]int,2)
for i:=0;i<len(numbers);i++{
for j:=i+1;j<len(numbers);j++{
if numbers[i]+numbers[j]==target{
result[0]= i+1
result[1] =j+1
}
}
}
return result
}
暴力解可以过也有点超出我的想象，我还以为会直接不给过。以前拿java做的时候好像是不过过的，但是嘛。暴力解肯定是不可取的
- runtime: 356 ms
- beats: 0%
- testcase: 16/16
- big O : n^2
解法1
看到有序，有序，有序，第一反应肯定是二分法。所以针对这道题，我们可以通过人二分法查找对应的值。
func twoSum(numbers []int, target int) []int {
result:=make([]int,2)
for i:=0;i<len(numbers);i++{
targetNumber:= target - numbers[i]
j:=binarySearch(numbers,i+1,len(numbers)-1,targetNumber)
if j!=-1{
result[0] = i+1
result[1] = j+1
return result
}
}
return result
}
func binarySearch(numbers[] int, start,end,target int) int{
left:= start
right:=end
for left<=right{
mid:=(left+right)>>1
if numbers[mid]==target{
return mid
}else if target<numbers[mid]{
right = mid-1
}else{
left = mid+1
}
}
return -1
}
就当练习下写二分查找咯
- runtime: 9 ms
- beats: 50.91%
- testcase: 16/16
- big O : nlogn
这个效率简直提升了不少啊，但是这个不是最优解哦，还可以把他变成n的时间复杂度呢
解法2
这里的做法就是双下标移动，给左边一个下标，右边也给一个。由于是有序的特性，所以，当target 大于 left+right的话，就说明 left+right 需要扩大，那么left 向右边移动，反之同理
func twoSum(numbers []int, target int) []int {
result :=make([]int,2)
left:=0
right:=len(numbers)-1
for left!=right{
if target == numbers[left]+numbers[right]{
result[0]=left+1
result[1]=right+1
return result
}else if target <numbers[left]+numbers[right]{
right--
}else{
left++
}
}
return result
}
- runtime: 9 ms
- beats: 50.91%
- testcase: 16/16
- big O : n testcase 的数据没有那么多 所有看不出差别，但是手动算复杂度还是可以算出来等于n的
No.238. Product of Array Except Self
Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
计算数组里面的所有累乘除去本身自己
暴力解法
func productExceptSelf(nums []int) []int {
result:=make([]int,len(nums))
for i:=range result{
result[i]= 1
}
for i:=0;i<len(nums);i++{
for j:=0;j<len(nums);j++{
if j!=i{
result[i]*=nums[j]
}
}
}
return result
}
- runtime: Time Limit Exceeded
- beats: Time Limit Exceeded
- testcase: Time Limit Exceeded
- big O : O(n^2)
解法1
题目要求，最后的时间复杂度要O(n),但是暴力解法的时间复杂度为O(n^2)，这次直接不让过了。根据题目要求不能使用除法。我们可以把乘法拆分成2部分
func productExceptSelf(nums []int) []int {
result:=make([]int,len(nums))
subResult:=1
for i:=range result{
result[i] = subResult
subResult *=nums[i]
}
subResult=1
for i:=len(nums)-1;i>-1;i--{
result[i] = subResult*result[i]
subResult *= nums[i]
}
return result
}
- runtime: 4162 ms
- beats: 3.3%
- testcase: 17/17
- big O : O(n)
No.442. Find All Duplicates in an Array
Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Could you do it without extra space and in O(n) runtime?
找出所有的重复的数字
暴力解法
比较传统的暴力解法，记录每个数字出现的个数，然后进行判断是不是等于2就好 当然 可以把数组换成 bool
func findDuplicates(nums []int) []int {
counts:=make([]int,len(nums))
result :=[]int{}
for i:=0;i<len(nums);i++{
counts[nums[i]-1] = counts[nums[i]-1]+1
if counts[nums[i]-1] == 2{
result = append(result,nums[i])
}
}
return result
}
- runtime: 1655 ms
- beats: 7.69%
- testcase: 28/28
- big O : O(n)
解法1
这道题目的要求，不能用额外的空间是，除了创建返回的数组 没有额外空间的消耗。 其实 1 ≤ a[i] ≤ n 这个条件是重点，隐含意思就是 所有的N都是大于0的。那么我们直接在原有的数组上进行操作。 如果出现了这个数字那么我们把对应位置的数字给变成负的
func findDuplicates(nums []int) []int {
result:=[]int{}
for i:=0;i<len(nums);i++{
var index int
if nums[i]<0{
index = -nums[i]-1
}else{
index = nums[i]-1
}
if nums[index]<0{
result= append(result,index+1)
}else{
nums[index] = -nums[index]
}
}
return result
}
- runtime: 1676 ms
- beats: 7.69%
- testcase: 28/28
- big O : O(n)
