算法

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
}

复杂度

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