2020-06-10:给定一个无序数组,里面数都是成双数的,只有一个数是成单数的,求这个数? 如果上面那题里面有两个单数,怎么求出来?

1.异或

2.字典或集合

3.排序

golang语言采用异或方式,代码如下:

package test22_singlenumber3

import (

"fmt"

    "testing"

)

//go test -v -test.run TestSingleNumber

func TestSingleNumber(t *testing.T) {

    arr := []int{3, 1, 2, 1, 3, 4, 4, 5}

    fmt.Println("数组:", arr)

    fmt.Println("结果:", singleNumber(arr))

}

func singleNumber(nums []int) []int {

    eorsum := 0 //两个单数的按位异或

    for i := len(nums) – 1; i >= 0; i– {

        eorsum ^= nums[i]

    }

    rightbit1 := eorsum & ((^eorsum) + 1) //取eorsum最右边的1

    retone := 0 //其中一个单数

    for i := len(nums) – 1; i >= 0; i– {

        if nums[i]&rightbit1 != 0 {

            retone ^= nums[i]

        }

    }

    return []int{eorsum ^ retone, retone}

}

敲go test -v -test.run TestSingleNumber命令,结果如下:


评论


发表评论

电子邮件地址不会被公开。 必填项已用*标注