算法

INFO

烦死了

摩尔投票法

  用于找出一堆数字中出现频率大于一半的算法，即找出众数。

实现方式

  遍历一次数组，记录两个值，一个是当前记录的数字和这个数字剩余的次数。

func majorityElement(nums []int) int {
	var maxNum int
	occurTime := 0
	for _, v := range nums {
		if v != maxNum {
			if occurTime == 0 {
				maxNum = v
				occurTime++
			} else {
                occurTime--
            }
		} else {
            occurTime++
        }
	}
    return maxNum
}

复杂度

• 时间复杂度：O(n)
• 空间负责度：O(1)

双指针

  经常用到，例如删除有序数组中的重复项，或者计算两数之和

删除有序数组中的重复项

func removeDuplicates(nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }
    slow := 1
    for fast := 1; fast < n; fast++ {
        if nums[fast] != nums[fast-1] {
            nums[slow] = nums[fast]
            slow++
        }
    }
    return slow
}

两数之和

  寻找一个非递减数组中两数之和等于某特定数字的两数。   初始时两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和，并和目标值比较。如果两个元素之和等于目标值，则发现了唯一解。如果两个元素之和小于目标值，则将左侧指针右移一位。如果两个元素之和大于目标值，则将右侧指针左移一位。移动指针之后，重复上述操作，直到找到答案。

KMP算法

  用来在一个主文本字符串中查找一个模式字符串的出现位置。大学数据结构中的经典算法，还是挺难的。

实现方式

  对于模式字符串，要先算一个next数组。next数组就是一个前缀表（prefix table）。前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。   前缀表代表的意思是该字符串中最长相同前后缀的长度，前后缀都是从左往右读。例如：aabaaf对应的前缀表就是010120

func computePrefix(pattern string) []int {
    prefix := make([]int, len(pattern))
    j := 0
    for i := 1; i < len(pattern); {
        if pattern[i] == pattern[j] {
            j++
            prefix[i] = j
            i++
        } else {
            if j != 0 {
                j = prefix[j-1]
            } else {
                prefix[i] = 0
                i++
            }
        }
    }
    return prefix
}

func kmpSearch(text, pattern string, next []int) []int {
  positions := []int{}
  j := 0
  
  for i := 0; i < len(text); {
    if text[i] == pattern[j] {
      i++
      j++
      
      if j == len(pattern) {
        positions = append(positions, i-j)
        j = next[j-1] // 继续寻找下一个匹配
      }
    } else {
      if j != 0 {
        j = next[j-1]
      } else {
        i++
      }
    }
  }
  return positions
}

  具体的比较方法，每次退回到next[j-1]。

复杂度

• 时间复杂度：O(m+n)

快速排序

package main

import (
    "fmt"
)

func quickSort(arr []int,l int,r int) {
  if l>=r {
    return
  }
  pivot,i,j:=arr[l+(r-l)/2],l,r
  for i<=j{
    for arr[i]<pivot {
      i++
    }
    for arr[j]>pivot {
      j--
    }
    if i<=j {
      arr[i], arr[j] = arr[j], arr[i]
      i++
      j--
    }
  }
  fmt.Println(l,r)
  fmt.Println(arr)
  quickSort(arr,l,j)
  quickSort(arr,i,r)
}

func main() {
    var n int
    fmt.Scanf("%d",&n)
    arr:=make([]int,n)
    for i:=0;i<n;i++{
      fmt.Scanf("%d",&arr[i])
    }
    quickSort(arr,0,len(arr)-1)
    for _,n := range arr {
      fmt.Printf("%d ",n)
    }

}

归并排序

package main

import (
  "fmt"
)

func mergeSort(arr []int) []int {
  if len(arr)==1 {
    return arr
  } else if len(arr)==2 {
    if arr[0]>arr[1] {
      arr[1],arr[0] = arr[0],arr[1]
    }
    return arr
  }
  middle := len(arr)/2
  left := mergeSort(arr[0:middle])
  right := mergeSort(arr[middle:])
  var temp_arr []int
  i,j := 0,0
  for {
    if i>=len(left) {
      temp_arr = append(temp_arr,right[j:]...)
      return temp_arr
    } else if j>=len(right) {
      temp_arr = append(temp_arr,left[i:]...)
      return temp_arr
    }
    if left[i]<right[j] {
      temp_arr = append(temp_arr,left[i])
      i++
    } else {
      temp_arr = append(temp_arr,right[j])
      j++
    }
  }
}

func main() {
  var k int
  fmt.Scanf("%d",&k)
  arr := make([]int,k)
  for i:=0;i<k;i++ {
    fmt.Scanf("%d",&arr[i])
  }
  arrs := mergeSort(arr)
  for i:=0;i<len(arrs);i++ {
    fmt.Printf("%d ",arrs[i])
  }
}