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

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

#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
}

有疑问加站长微信联系（非本文作者）