初练算法,比较算法之美

作为一名coder,算法不仅要会懂会写,在保证结果正确的同时,还要求性能足够高,才称得上优秀的算法。

本文比较了本人用 golang 初练算法的一些 demo,以期不断进步,假以时日,写出更好的算法。

1. 求众数(在数组中出现次数大于 n/2 的元素)

a. 本人写法:

func majorityElement1(nums []int) int {
 n := len(nums)
 for i := 0; i < n; i++ {
 equalNum := 1
 for j := 0; j < n; j++ {
 if nums[i] == nums[j] && i != j {
 equalNum++
 }
 if equalNum > n/2 {
 return nums[i]
 }
 }
 }
 return nums[0]
}

b. 别人优秀写法:

func majorityElement2(nums []int) int {
 middle := len(nums) / 2
 equalMap := make(map[int]int, middle)
 for _, v := range nums {
 equalMap[v] += 1
 if equalMap[v] > middle {
 return v
 }
 }
 return nums[0]
}

2. 只出现一次的数字

a. 本人写法:

func singleNumber1(nums []int) int {
 n := len(nums)
 for i := 0; i < n; i++ {
 for j := 0; j < n; j++ {
 if nums[i] == nums[j] && i != j {
 break
 }
 if j == (n - 1) {
 return nums[i]
 }
 }
 }
 return nums[n-1]
}

b. 别人优秀写法:

func singleNumber2(nums []int) int {
 // 零和任何数异或都等于任何数, 一个数异或两次就等于0
 // 本题中除一个之外每个元素都出现两次
 // 所以用循环异或所有数就等于 只出现一次的那个数
 ret := 0
 for _, v := range nums {
 ret ^= v
 }
 return ret
}

3. 搜索二位矩阵中的值

a. 本人写法:

func searchMatrix1(matrix [][]int, target int) bool {
 ret := false
 for i, _ := range matrix {
 if ret {
 break
 }
 for _, inValue := range matrix[i] {
 if inValue == target {
 ret = true
 break
 }
 }
 }
 return ret
}

b. 别人优秀写法:

func searchMatrix2(matrix [][]int, target int) bool {
 if len(matrix) == 0 {
 return false
 }
 row, col := len(matrix), len(matrix[0])
 i, j := 0, col-1
 for i < row && j >= 0 {
 if matrix[i][j] == target {
 return true
 }
 if matrix[i][j] > target {
 j--
 } else if matrix[i][j] < target {
 i++
 }
 }
 return false
}

4. 合并两个有序数组

a. 本人写法:

func merge1(nums1 []int, m int, nums2 []int, n int) {
 nonZero := 0
 for i, _ := range nums1 {
 if nums1[i] != 0 {
 nonZero = i
 break
 }
 }
 length := len(nums1)
 for i := 0; i < length; i++ {
 if nums1[i] == 0 {
 if length == 1 {
 nums1 = []int{}
 break
 }
 if i > nonZero {
 nums1 = append(nums1[:i], nums1[i+1:]...)
 i--
 }
 length = len(nums1)
 }
 }
 m = len(nums1)
 if m <= 0 || len(nums1) == 0 {
 nums1 = append(nums1, nums2...)
 } else {
 for i := 0; i < m; i++ {
 if len(nums1) == m+n {
 break
 }
 for index := 0; index < n; index++ {
 // corner case
 if nums2[0] >= nums1[m-1] && i == 0 && index == 0 {
 nums1 = append(nums1, nums2...)
 break
 }
 if nums2[n-1] <= nums1[0] && i == 0 && index == 0 {
 nums1 = append(nums2, nums1...)
 break
 }
 if nums2[index] > nums1[i] {
 if i == len(nums1)-1 {
 nums1 = append(nums1, nums2[index:]...)
 break
 }
 i++
 if index != n-1 {
 index--
 } else {
 nums1 = append(nums1, nums2[n-1])
 break
 }
 continue
 }
 if nums2[index] == nums1[i] {
 rear := append([]int{}, nums1[i+1:]...)
 nums1 = append(nums1[0:i+1], nums2[index])
 nums1 = append(nums1, rear...)
 i++
 continue
 }
 if nums2[index] < nums1[i] {
 if index == 0 && i == 0 {
 nums1 = append([]int{nums2[index]}, nums1...)
 } else {
 rear := append([]int{}, nums1[i:]...)
 nums1 = append(nums1[0:i], nums2[index])
 nums1 = append(nums1, rear...)
 }
 i++
 continue
 }
 }
 }
 }
 fmt.Println(nums1)
}

b. 别人优秀写法:

func merge2(nums1 []int, m int, nums2 []int, n int) {
 for i := 0; i < n; i++ {
 nums1[m+i] = nums2[i]
 }
 sort.Sort(sort.IntSlice(nums1))
 fmt.Println(nums1)
}

这个题目,自己花了很多时间才写出来,看了别人的写法后,反思自己怎么没有想到用 golang 自带的排序函数 : (

所以做事情之前要先想到是否别人已经有造好的轮子(当然轮子要是已经被广泛认可的)可用,站在巨人的肩膀上才能走的更远。

小结:

从以上例子看出,在写算法,我目前的思路总是想着循环嵌套去实现,虽然能计算出正确的结果,但性能很低,所以需要不断学习别人优秀的算法思路,不断动手练习,期望以后也可以随手写出优秀的算法。

祝大家周末愉快~

本文来自:Segmentfault

感谢作者:热爱coding的稻草

查看原文:初练算法,比较算法之美

• 编辑
• 预览