leetcode刷题记录Array篇(1&4~Two Sum&Median of Two Sorted Arrays)

L千年老妖 · · 873 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

今天写了一道比较简单的和一道难的
#Two Sum

题目:Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element
twice.

简单翻译,就是在一个数组中寻找相加和target值相等的两个数的下标,只要返回最先匹配的,并且下标相等的不算。

golang代码:

package main

import (
"fmt"
)

 func main() {
nums := []int{2, 7, 11, 15}
fmt.Println(twoSum(nums, 9))
 }

//自己的版本 O(n^2)
// func twoSum(nums []int, target int) []int {
 //     arr := []int{}
//     for index, val := range nums {
//         for index1, val2 := range nums {
//             if val+val2 == target && index != index1 {
//                 arr = []int{index, index1}
//                 return arr
//             }
//         }
//     }
//     return arr
// }

 //时间复杂度小的 O(n)
func twoSum(nums []int, target int) []int {

  arr := []int{}
  container := make(map[int]int)
  for i := 0; i < len(nums); i++ {
    if xy, ok := container[target-nums[i]]; ok && xy != i {
        arr = []int{container[target-nums[i]], i}
        return arr
    }
    container[nums[i]] = i
   }
   return arr
 }
#

题目:There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

简单翻译:计算中位数,时间复杂度为O(log(m+n)),我的没能达到要求,因为写博客才发现这后面的要求,不过通过了测试,但是速度相对来说比较慢

golang代码:

package main

   import (
  "fmt"
    )

 func main() {
nums1 := []int{1, 87, 9}
nums2 := []int{2, 5, 6}
fmt.Println(findMedianSortedArrays(nums1, nums2))
}

 func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {

l1, l2 := len(nums1), len(nums2)
numbers1 := make([]float64, l1)
numbers2 := make([]float64, l2)

//合并两个数组
mergeArr := make([]float64, len(nums1)+len(nums2))
for i, val := range nums1 {
    numbers1[i] = float64(val)
}
for i, val := range nums2 {
    numbers2[i] = float64(val)
}
copy(mergeArr, numbers1)
copy(mergeArr[len(nums1):], numbers2)

//排序(冒泡)
var temp float64
var middle float64
length := len(mergeArr)

for i := 0; i < length-1; i++ {
    for j := 0; j < length-i-1; j++ {
        if mergeArr[j] > mergeArr[j+1] {
            temp = mergeArr[j]
            mergeArr[j] = mergeArr[j+1]
            mergeArr[j+1] = temp
        }
    }
}
if length == 0 {
    middle = 0
} else if length%2 == 0 {
    fmt.Println((mergeArr[length/2] + mergeArr[length/2-1]) / 2)
    middle = (mergeArr[length/2] + mergeArr[length/2-1]) / 2
} else {
    middle = float64(mergeArr[length/2])
}
return middle
}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:L千年老妖

查看原文:leetcode刷题记录Array篇(1&4~Two Sum&Median of Two Sorted Arrays)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

873 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传