英文:
Golang: find first character in a String that doesn't repeat
问题
我正在尝试编写一个函数,该函数返回字符串中第一个不重复的字符。到目前为止,我有以下代码:
package main
import (
"fmt"
"strings"
)
func check(s string) string {
ss := strings.Split(s, "")
smap := map[string]int{}
for i := 0; i < len(ss); i++ {
(smap[ss[i]])++
}
for k, v := range smap {
if v == 1 {
return k
}
}
return ""
}
func main() {
fmt.Println(check("nebuchadnezzer"))
}
不幸的是,在Go语言中,当你迭代一个map时,不能保证顺序,所以每次运行代码时我都会得到不同的值。有什么建议吗?
英文:
I'm trying to write a function that returns the finds first character in a String that doesn't repeat, so far I have this:
package main
import (
"fmt"
"strings"
)
func check(s string) string {
ss := strings.Split(s, "")
smap := map[string]int{}
for i := 0; i < len(ss); i++ {
(smap[ss[i]])++
}
for k, v := range smap {
if v == 1 {
return k
}
}
return ""
}
func main() {
fmt.Println(check("nebuchadnezzer"))
}
Unfortunately in Go when you iterate a map there's no guarantee of the order so every time I run the code I get a different value, any pointers?
答案1
得分: 6
使用地图和2个循环:
play
func check(s string) string {
m := make(map[rune]uint, len(s)) //预分配地图大小
for _, r := range s {
m[r]++
}
for _, r := range s {
if m[r] == 1 {
return string(r)
}
}
return ""
}
这样做的好处是只使用2个循环,而不是多个循环,如果你使用strings.ContainsRune
,strings.IndexRune
(每个函数中都会有内部循环)。
英文:
Using a map and 2 loops :
play
func check(s string) string {
m := make(map[rune]uint, len(s)) //preallocate the map size
for _, r := range s {
m[r]++
}
for _, r := range s {
if m[r] == 1 {
return string(r)
}
}
return ""
}
The benfit of this is using just 2 loops vs multiple loops if you're using strings.ContainsRune
, strings.IndexRune
(each function will have inner loops in them).
答案2
得分: 2
高效(时间和内存)的算法,用于获取所有或第一个唯一的字节<http://play.golang.org/p/ZGFepvEXFT>:
func FirstUniqueByte(s string) (b byte, ok bool) {
occur := [256]byte{}
order := make([]byte, 0, 256)
for i := 0; i < len(s); i++ {
b = s[i]
switch occur[b] {
case 0:
occur[b] = 1
order = append(order, b)
case 1:
occur[b] = 2
}
}
for _, b = range order {
if occur[b] == 1 {
return b, true
}
}
return 0, false
}
作为额外的奖励,上述函数不应生成任何垃圾。请注意,我更改了您的函数签名,以更符合表达您所描述的方式。如果您仍然需要一个func(string) string
的签名,那么这一点就无关紧要了。
英文:
Efficient (in time and memory) algorithms for grabbing all or the first unique byte <http://play.golang.org/p/ZGFepvEXFT>:
func FirstUniqueByte(s string) (b byte, ok bool) {
occur := [256]byte{}
order := make([]byte, 0, 256)
for i := 0; i < len(s); i++ {
b = s[i]
switch occur[b] {
case 0:
occur[b] = 1
order = append(order, b)
case 1:
occur[b] = 2
}
}
for _, b = range order {
if occur[b] == 1 {
return b, true
}
}
return 0, false
}
As a bonus, the above function should never generate any garbage. Note that I changed your function signature to be a more idiomatic way to express what you're describing. If you need a func(string) string
signature anyway, then the point is moot.
答案3
得分: 0
这可以进行优化,但一个解决方案(不使用map)是:
func check(s string) string {
unique := ""
for pos, c := range s {
if strings.ContainsRune(unique, c) {
unique = strings.Replace(unique, string(c), "", -1)
} else if strings.IndexRune(s, c) == pos {
unique = unique + string(c)
}
}
fmt.Println("All unique characters found: ", unique)
if len(unique) > 0 {
_, size := utf8.DecodeRuneInString(unique)
return unique[:size]
}
return ""
}
这是在问题“在字符串中找到第一个不重复的字符”之后的代码。
krait建议该函数应该返回一个包含第一个完整rune的字符串,而不仅仅是第一个rune的utf8编码的第一个字节。
英文:
That can certainly be optimized, but one solution (which isn't using map) would be:
(playground example)
func check(s string) string {
unique := ""
for pos, c := range s {
if strings.ContainsRune(unique, c) {
unique = strings.Replace(unique, string(c), "", -1)
} else if strings.IndexRune(s, c) == pos {
unique = unique + string(c)
}
}
fmt.Println("All unique characters found: ", unique)
if len(unique) > 0 {
_, size := utf8.DecodeRuneInString(unique)
return unique[:size]
}
return ""
}
This is after the question "Find the first un-repeated character in a string"
krait suggested below that the function should:
> return a string containing the first full rune, not just the first byte of the utf8 encoding of the first rune.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论