go 实现[找到小镇的法官]

题目

在一个小镇里,按从 1 到 N 标记了 N 个人。传言称,这些人中有一个是小镇上的秘密法官。

如果小镇的法官真的存在,那么:

小镇的法官不相信任何人。
每个人(除了小镇法官外)都信任小镇的法官。
只有一个人同时满足属性 1 和属性 2 。
给定数组 trust,该数组由信任对 trust[i] = [a, b] 组成,表示标记为 a 的人信任标记为 b 的人。

如果小镇存在秘密法官并且可以确定他的身份,请返回该法官的标记。否则,返回 -1。

题解

方法1

1、定义两个切片, 分别代表信任切片和被信任切片

2、遍历传入的切片,拿到信任数据,已该数据为下标,把该下标对应的信任切片的值加1,代表此人信任他人数量加1;同理拿到被信任数据,已该数据为下标,把该下标对应的被信任的切片值加1,代表此人被他人信任的数量1.

3、待数据遍历完成后,遍历被信任切片,只要对应下标的数据(即被别人信任的数量)为 N-1,并且信任切片里对应下标的数据为零(即此人不相信任何人)。那么此下标对应的人即是法官。 严格一些的话,需要遍历完切片,如果存在相同情况。那么也会出现没有法官的情况。

方法2

1、定义两个切片, 分别代表信任切片和被信任切片

2、定义两个集合,分别代表信任集合和所有元素集合

3、遍历传入的切片,拿到信任数据,已该数据为下标,把该下标对应的信任切片的值加1,代表此人信任他人数量加1。同时把该下标加入信任集合和所有元素集合;同理拿到被信任数据,已该数据为下标,把该下标对应的被信任的切片值加1,代表此人被他人信任的数量1。同时把下标加入所有元素的集合。

4、对两个集合求差集,剩余集合里的人是有可能成为法官的人

5、遍历剩余集合,只要对应下标的数据(即被别人信任的数量)为 N-1,并且信任切片里对应下标的数据为零(即此人不相信任何人)。那么此下标对应的人即是法官。 与方法1 一样, 严格一些的话,需要遍历完剩余集合,如果存在相同情况。那么也会出现没有法官的情况。

代码

package main

import (
	"fmt"
	//mapset "github.com/deckarep/golang-set"
)

func findJudge(N int, trust [][]int) int {

	//trustset := mapset.NewSet()
	//allset := mapset.NewSet()
	trustSlie := make([]int, 2000)
	beTrustedSlice := make([]int, 2000)
	if N == 1 {
		return N
	}
	if N >= 2000 {
		fmt.Println("slice index out of range")
		return -1
	}
	leng := len(trust)
	for i := 0; i < leng; i++ {
		//trustset.Add(trust[i][0])
		//allset.Add(trust[i][0])
		//allset.Add(trust[i][1])
		trustSlie[trust[i][0]]++
		beTrustedSlice[trust[i][1]]++
	}
	//canjudge := allset.Difference(trustset)

	//for elem := range canjudge.Iter() {
	//		elem.(int), beTrustedSlice[elem.(int)], trustSlie[elem.(int)], N-1)
	//	if (N - 1) == (beTrustedSlice[elem.(int)] - trustSlie[elem.(int)]) {
	//		return elem.(int)
	//	}
	//}
	for index, elem := range beTrustedSlice {
		if (elem == N-1) && (trustSlie[index] == 0) {
			return index
		}
	}
	return -1
}

func main() {

	test := [][]int{{1, 3}, {2, 3}}

	fmt.Println(findJudge(3, test))
}
原文地址:https://www.cnblogs.com/HavenBlog/p/14351938.html