Dominator

Find an index of an array such that its value occurs at more than half of indices in the array.

An array A consisting of N integers is given. The dominator of array A is the value that occurs in more than half of the elements of A.

For example, consider array A such that

A[0] = 3 A[1] = 4 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = -1 A[6] = 3 A[7] = 3 The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.

Write a function

func Solution(A []int) int

that, given an array A consisting of N integers, returns index of any element of array A in which the dominator of A occurs. The function should return −1 if array A does not have a dominator.

For example, given array A such that

A[0] = 3 A[1] = 4 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = -1 A[6] = 3 A[7] = 3 the function may return 0, 2, 4, 6 or 7, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000]; each element of array A is an integer within the range [−2,147,483,648..2,147,483,647]. Copyright 2009–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

題目大意

返回Array中的支配數. A的支配數是3，因為它出現在A的8個元素中的5個元素中(index為0、2、4、6和7). 而5是8的一半以上 可以返回 0,2,4,6,7中的任一數

解題思路

用map紀錄每筆數出現次數. 取最大次數看是否有超過一半以上. 是的話返回此數任一個index, 反之返回-1

來源

https://app.codility.com/programmers/lessons/8-leader/dominator/

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Codility/Lesson/0008.Leader/Dominator/Dominator.go

package Dominator

import (
    "math"
)

func Solution(A []int) int {
    mapInt := make(map[int]int, len(A))

    for _, v := range A {
        if _, ok := mapInt[v]; !ok {
            mapInt[v] = 1
        } else {
            mapInt[v]++
        }
    }

    maxCount := 0
    maxVal := 0
    for k, v := range mapInt {
        if v > maxCount {
            maxCount = v
            maxVal = k
        }
    }
    minIndex := -1
    for k, v := range A {
        if v == maxVal {
            minIndex = k
            break
        }
    }

    if maxCount > int(math.Floor(float64(len(A))/2.0)) {
        return minIndex
    } else {
        return -1
    }
}