Contents

1. 1. 面试算法题记录01

面试算法题记录01

问题:

整型数组长度为n,内部有一个元素出现的数量大于n>>1,请设计一个算法求出这个元素
要求时间复杂度为O(n)空间复杂度O(1)

分析:

n>>1.就是把n除以2的1次方,即该元素出现的次数大于一半

代码:Swift

func getElement(_ array: [Int]) -> Int? {
    var currentItem : Int? // 当前的元素
    var currentFlag = 0 // 该数字为0的时候表示,在这之前遍历的元素中重复的和不重复的持平

    for item in array {
        if currentFlag == 0 {//当前的元素出现的数量超出平衡,需要缓存一下
            currentItem = item
            currentFlag = 1
        }
        else if currentItem == item {
            currentFlag += 1
        }
        else if currentItem != item {
            currentFlag -= 1
        }
    }

    return currentItem
}

/*:
 分析:
 > 根据元素个数,向右位移1为,即为出现的次数
 > 10个元素(1010),这里就需要大于5(0101)
 > 右移n位相当于除以2的n次方
 */

let array = [1,3,3,4,3,3,3,3,3,1]
getElement(array)