描述

一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

数据范围：数组长度 2≤n≤1000，数组中每个数的大小 0 < val ≤ 1000000
要求：空间复杂度 O(1)，时间复杂度 O(n)

提示：输出时按非降序排列。

示例

// 输入：
[1,4,1,6]
// 返回值：
[4,6]
// 说明：返回的结果中较小的数排在前面

// 输入：
[1,2,3,3,2,9]
// 返回值：
[1,9]

解题思路

哈希法：

• 先遍历数组，以数为键名，出现次数为键值存入map（也可以是 array）
• 再遍历 map，找出 val 为 1 的两个数，组成数组
• 判断两个数大小，从小到大排序

代码实现

/**
 * [JZ56-中等] 数组中只出现一次的两个数字
 *
 * @param array int整型一维数组
 * @return int整型一维数组
 */
func findNumsAppearOnce(array []int) []int {
    hash := map[int]int{}

    // 统计每个数出现的次数
    for _, v := range array {
        if _, ok := hash[v]; ok {
            hash[v] += 1
        } else {
            hash[v] = 1
        }
    }

    // 遍历查找次数等于 1 的数
    result := []int{}
    for k, v := range hash {
        if v == 1 {
            result = append(result, k)
        }
    }

    // 排序 - 就两个数，判断下大小即可
    for i := 0; i < len(result)-1; i++ {
        if result[i] > result[i+1] {
            result[i], result[i+1] = result[i+1], result[i]
        }
    }

    return result
}