René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"【问题Q\u0026A】收集","articleBody":"\u003e Q: 这里的时间复杂度是 n 还是 n^2\r\n\r\n```go\r\nfunc moveZeroes(nums []int)  {\r\n    j:=0\r\n    for i:=0; i\u003clen(nums); i++{\r\n        if nums[j] == 0 {\r\n            // nums = append(nums[:j], append(nums[j+1:], nums[j])...)\r\n            nums = append(nums[:j], nums[j+1:]...)\r\n\t\t\tnums = append(nums, 0)\r\n            j--\r\n        }\r\n        j++\r\n    }\r\n}\r\n```\r\n\r\nA: 这里值得注意的是 ` nums = append(nums[:j], nums[j+1:]...)` 这条语句， 它的作用不是 添加而是删除 下标为 j 的元素，**在数组中，插入和删除元素的时间复杂度是 O(n)**, 由于外层 for 循环 的关系，这里的整体时间复杂度是 O(n^2)\r\n\r\n\r\n\r\n\r\n\u003e Q: 检测环的时候使用快慢指针，走2步和走多步哪个效率高，怎么证明？\r\n\r\nhttps://code-examples.net/zh-CN/q/4e4806\r\n\r\n\r\n\r\n\u003e Q: 网上说链表和数组的插入性能都是o(n) ，这块是什么情况？\r\n\r\nA: 数组的插入 O(n) 的复杂度毫无疑问，但是链表的插入为 O(n) 是有问题的，在这里，**链表在某个点插入新的结点的时间复杂度是 O(1), 但是在找到这个位置的过程时间复杂度是 O(n)**, 注意把握概念。\r\n","author":{"url":"https://github.com/GeekUniversity","@type":"Person","name":"GeekUniversity"},"datePublished":"2020-05-09T08:12:49.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":2},"url":"https://github.com/49/algorithm008-class02/issues/49"}