求助,leetcode的问题?

qiuquanwu · 2018-05-13 22:28:21 · 1112 次点击 · 大约8小时之前 开始浏览    置顶
这是一个创建于 2018-05-13 22:28:21 的主题,其中的信息可能已经有所发展或是发生改变。


有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1112 次点击  
加入收藏 微博
7 回复  |  直到 2018-05-16 10:41:33
justay
justay · #1 · 7年之前
func removeDuplicates(nums []int) int {
    p:=0
    ct:=0
    idx:=0
    for i,v:=range nums {
        if i==0 {
            p = v
            ct = ct + 1
            idx = idx + 1
            continue
        }
        if v!=p {
            nums[idx]=v
            ct = ct +1
            p = v
            idx = idx + 1
        }
    }   
    return ct
}
13728605342
13728605342 · #2 · 7年之前

这里有中文版本的解析,可以看看,希望能帮到你:https://cloud.tencent.com/developer/doc/1101

killernova
killernova · #3 · 7年之前
justayjustay #1 回复

```golang func removeDuplicates(nums []int) int { p:=0 ct:=0 idx:=0 for i,v:=range nums { if i==0 { p = v ct = ct + 1 idx = idx + 1 continue } if v!=p { nums[idx]=v ct = ct +1 p = v idx = idx + 1 } } return ct } ```

你有3个变量,那就是O(3)了吧

killernova
killernova · #4 · 7年之前
func removeDuplicates(nums []int) []int {
    if len(nums) <= 1 {
        return nums
    }
    for i := 1; ; {
        if i > len(nums)-1 {
            break
        }
        if nums[i] == nums[i-1] {
            nums = append(nums[0:i], nums[i+1:]...)
        } else {
            i++
        }

    }
    return nums
}
killernova
killernova · #5 · 7年之前
killernovakillernova #4 回复

```go func removeDuplicates(nums []int) []int { if len(nums) <= 1 { return nums } for i := 1; ; { if i > len(nums)-1 { break } if nums[i] == nums[i-1] { nums = append(nums[0:i], nums[i+1:]...) } else { i++ } } return nums } ```

题目是要求返回长度,忘记改了。

justay
justay · #6 · 7年之前
killernovakillernova #3 回复

#1楼 @justay 你有3个变量,那就是O(3)了吧

这段代码可以优化成

func removeDuplicates(nums []int) int {
    idx := 0
    for i, v := range nums {
        if i == 0 {
            idx = idx + 1
            continue
        }
        if v != nums[idx-1] {
            nums[idx] = v
            idx = idx + 1
        }
    }
    return idx
}

和你的算法做了下benchmark的比较

$ go test -bench=".*"
goos: windows
goarch: amd64
Benchmark_solA_1-8      100000000               18.5 ns/op
Benchmark_solB_1-8      50000000                31.3 ns/op
Benchmark_solA_2-8      30000000                58.3 ns/op
Benchmark_solB_2-8       5000000               294 ns/op
PASS

solA是上面的程序,solB是你的算法,其实可以看出append操作还是比较耗时间的。

另外,我觉得这个题目不太合适go,毕竟传过来的nums又不一定是原来的nums。

killernova
killernova · #7 · 7年之前
justayjustay #6 回复

#3楼 @killernova 这段代码可以优化成 ```golang func removeDuplicates(nums []int) int { idx := 0 for i, v := range nums { if i == 0 { idx = idx + 1 continue } if v != nums[idx-1] { nums[idx] = v idx = idx + 1 } } return idx } ``` 和你的算法做了下benchmark的比较 ```golang $ go test -bench=".*" goos: windows goarch: amd64 Benchmark_solA_1-8 100000000 18.5 ns/op Benchmark_solB_1-8 50000000 31.3 ns/op Benchmark_solA_2-8 30000000 58.3 ns/op Benchmark_solB_2-8 5000000 294 ns/op PASS ``` solA是上面的程序,solB是你的算法,其实可以看出append操作还是比较耗时间的。 另外,我觉得这个题目不太合适go,毕竟传过来的nums又不一定是原来的nums。

题目要求原地删除重复元素,你这个方法貌似没有删除元素啊?

添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传