Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitaac776e

Browse files
authored
Merge pull request6boris#91 from 2yuechanghe/master
add 287 solution
2 parents4368d40 +a963c9b commitaac776e

File tree

3 files changed

+177
-0
lines changed

3 files changed

+177
-0
lines changed
Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
#[#[1. Add Sum][title]
2+
3+
##Description
4+
5+
给定一个数组 nums 包含 n + 1 个整数，每个整数在 1 到 n 之间，包括 1 和 n。现在假设数组中存在一个重复的数字，找到该重复的数字。
6+
7+
注意
8+
不能修改数组元素，假设数组是只读的。
9+
仅可以使用常数即O(1)O(1)的额外空间。
10+
时间复杂度需要低于O(n2)O(n2)。
11+
数组中仅有一个重复数字，但它可能重复超过1次。
12+
13+
**Example 1:**
14+
15+
```
16+
Example 1:
17+
18+
Input: [1,3,4,2,2]
19+
Output: 2
20+
Example 2:
21+
22+
Input: [3,1,3,4,2]
23+
Output: 3
24+
```
25+
26+
**Tags:** Math, String
27+
28+
##题意
29+
>这道题目主要应用了抽屉原理和分治的思想。
30+
31+
抽屉原理：n+1 个苹果放在 n 个抽屉里，那么至少有一个抽屉中会放两个苹果。
32+
33+
用在这个题目中就是，一共有 n+1 个数，每个数的取值范围是1到n，所以至少会有一个数出现两次。
34+
35+
然后我们采用分治的思想，将每个数的取值的区间[1, n]划分成[1, n/2]和[n/2+1, n]两个子区间，然后分别统计两个区间中数的个数。
36+
注意这里的区间是指 数的取值范围，而不是 数组下标。
37+
38+
划分之后，左右两个区间里一定至少存在一个区间，区间中数的个数大于区间长度。
39+
这个可以用反证法来说明：如果两个区间中数的个数都小于等于区间长度，那么整个区间中数的个数就小于等于n，和有n+1个数矛盾。
40+
41+
因此我们可以把问题划归到左右两个子区间中的一个，而且由于区间中数的个数大于区间长度，根据抽屉原理，在这个子区间中一定存在某个数出现了两次。
42+
43+
依次类推，每次我们可以把区间长度缩小一半，直到区间长度为1时，我们就找到了答案。
44+
45+
作者：extrovert
46+
链接：https://www.acwing.com/solution/LeetCode/content/2814/
47+
来源：AcWing
48+
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
49+
50+
- 复杂度分析
51+
时间复杂度：每次会将区间长度缩小一半，一共会缩小 O(logn) 次。每次统计两个子区间中的数时需要遍历整个数组，时间复杂度是 O(n)。所以总时间复杂度是 O(nlogn)。
52+
空间复杂度：代码中没有用到额外的数组，所以额外的空间复杂度是 O(1)。
53+
54+
##题解
55+
56+
###思路1
57+
>。。。。
58+
59+
```go
60+
61+
```
62+
63+
###思路2
64+
>思路2
65+
```go
66+
67+
```
68+
69+
##结语
70+
71+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
72+
73+
[title]:https://leetcode.com/problems/two-sum/description/
74+
[me]:https://github.com/kylesliu/awesome-golang-leetcode
Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package Solution
2+
3+
import (
4+
"math"
5+
"sort"
6+
)
7+
8+
//二分
9+
funcfindDuplicate(nums []int)int {
10+
left,right:=0,len(nums)-1
11+
forleft<right {
12+
mid:= (left+right)/2
13+
count:=0
14+
for_,num:=rangenums {
15+
ifnum<=mid {
16+
count++
17+
}
18+
}
19+
ifcount>mid {
20+
right=mid
21+
}else {
22+
left=mid+1
23+
}
24+
}
25+
returnleft
26+
}
27+
28+
//排序
29+
funcfindDuplicate2(nums []int)int {
30+
sort.Ints(nums)
31+
fori:=1;i<len(nums);i++ {
32+
ifnums[i]==nums[i-1] {
33+
returnnums[i]
34+
}
35+
}
36+
return0
37+
}
38+
39+
//map
40+
funcfindDuplicate3(nums []int)int {
41+
found:=-1
42+
m:=make(map[int]int)
43+
for_,v:=rangenums {
44+
m[v]++
45+
ifm[v]>1 {
46+
found=v
47+
break
48+
}
49+
}
50+
returnfound
51+
}
52+
53+
//排序
54+
funcfindDuplicate4(nums []int)int {
55+
fori:=rangenums {
56+
tmp:=int(math.Abs(float64(nums[i])))
57+
ifnums[tmp-1]<0 {
58+
returnint(math.Abs(float64(nums[i])))
59+
}
60+
nums[tmp-1]=-nums[tmp-1]
61+
}
62+
return-1
63+
}
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package Solution
2+
3+
import (
4+
"reflect"
5+
"strconv"
6+
"testing"
7+
)
8+
9+
funcTestSolution(t*testing.T) {
10+
//测试用例
11+
cases:= []struct {
12+
namestring
13+
inputs []int
14+
expectint
15+
}{
16+
{"TestCase", []int{1,3,4,2,2},2},
17+
{"TestCase", []int{3,1,3,4,2},3},
18+
}
19+
20+
//开始测试
21+
fori,c:=rangecases {
22+
t.Run(c.name+" "+strconv.Itoa(i),func(t*testing.T) {
23+
got:=findDuplicate(c.inputs)
24+
if!reflect.DeepEqual(got,c.expect) {
25+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
26+
c.expect,got,c.inputs)
27+
}
28+
})
29+
}
30+
}
31+
32+
//压力测试
33+
funcBenchmarkSolution(b*testing.B) {
34+
35+
}
36+
37+
//使用案列
38+
funcExampleSolution() {
39+
40+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp