数组专题

LeetCode136.只出现一次的数字

题目描述：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例：

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

算法代码：

func singleNumber(nums []int) int {
    single := 0
    for _,num := range nums {
        single ^= num
    }
    return single
}

算法思路：

只有一个数字只出现一次，其他数字都出现两次，相同数字位运算结果为0，单独数字和0做位运算结果为他本身。

即只需要对整个数组做位运算，可以找出唯一单独的数字。

LeetCode169.多数元素

题目描述：

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例：

示例 1：

输入：[3,2,3]
输出：3

示例 2：

输入：[2,2,1,1,1,2,2]
输出：2

算法代码：

func majorityElement(nums []int) int {
    major := 0
    count := 0
    for _,num := range nums{
        if count == 0 {
            major = num
        }
        if major == num {
            count ++
        }else{
            count --
        }
    }
    return najor
}

算法思路：

摩尔投票法：利用相互抵消的概念

排序法： 排序之后的中间值一定为众数

func majorityElement(nums []int) int {
    sort.Ints(nums)
    index := len(nums)
    return nums[len/2]
}

LeetCode15.三数之和

题目描述：

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：

答案中不可以包含重复的三元组。

示例：

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]

提示：

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

算法代码：

func threeSum(nums []int) [][]int {
    n := len(nums)
    sort.Ints(nums)
    //ans := make([][]int, 0)
    ans := [][]int{}

    // 枚举 a
    for first := 0; first < n; first++ {
        // 需要和上一次枚举的数不相同
        if first > 0 && nums[first] == nums[first - 1] {
            continue
        }
        // c 对应的指针初始指向数组的最右端
        third := n - 1
        target := -1 * nums[first]
        // 枚举 b
        for second := first + 1; second < n; second++ {
            // 需要和上一次枚举的数不相同
            if second > first + 1 && nums[second] == nums[second - 1] {
                continue
            }
            // 需要保证 b 的指针在 c 的指针的左侧
            for second < third && nums[second] + nums[third] > target {
                third--
            }
            // 如果指针重合，随着 b 后续的增加
            // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
            if second == third {
                break
            }
            if nums[second] + nums[third] == target {
                ans = append(ans, []int{nums[first], nums[second], nums[third]})
            }
        }
    }
    return ans
}

算法思路：

排序加双指针的思想

算法改进：

func threeSum(nums []int)[][]int{
	n := len(nums)
    sort.Ints(nums)
    ans := [][]int{}
    for first := 0 ; first < n - 2 ; first ++ {
        n1 := nums[first]
        if n1 > 0 {
            break
        }
        if first > 0 && nums[first] == nums[first - 1] {
            continue
        }
        second , third := first + 1 , n - 1
        for second < third {
            n2 , n3 := nums[second] , nums[third]
            if n1 + n2 + n3 == 0 {
                ans = append(ans , []int {n1 , n2 , n3})
                for second < third && nums[second] == n2 {
                    second ++
                }
                for second < third && nums[third] == n3 {
                    third --
                }
            }else if n1 + n2 + n3 < 0 {
                second ++
            }else {
                third --
            }
        }
    }
    return ans
}