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

Commit53c07e0

Browse files
committed
🐱 Add Problem 169 of 5 Solutions
1 parentbf963a5 commit53c07e0

File tree

3 files changed

+475
-0
lines changed

3 files changed

+475
-0
lines changed

‎src/0169.Majority-Element/README.md

Lines changed: 155 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,155 @@
1+
#[169. Majority Element][title]
2+
3+
##Description
4+
5+
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
6+
7+
You may assume that the array is non-empty and the majority element always exist in the array.
8+
**Example 1:**
9+
10+
```
11+
Input: [3,2,3]
12+
Output: 3
13+
```
14+
15+
**Example 2:**
16+
17+
```
18+
Input: [2,2,1,1,1,2,2]
19+
Output: 2
20+
```
21+
22+
**Tags:** Math, String
23+
24+
##题意
25+
>在一个数组除寻找出现次数超过一半的数
26+
27+
##题解
28+
29+
###思路1
30+
>暴力2层循环
31+
32+
```go
33+
funcmajorityElement(nums []int)int {
34+
major,count:= nums[0],0
35+
36+
for_,v1:=range nums {
37+
tmpCount:=0
38+
for_,v2:=range nums {
39+
if v2 == v1 {
40+
tmpCount++
41+
}
42+
}
43+
if tmpCount > count {
44+
count = tmpCount
45+
major = v1
46+
}
47+
}
48+
49+
return major
50+
}
51+
```
52+
53+
###思路2
54+
>Map 计数
55+
56+
```go
57+
funcmajorityElement(nums []int)int {
58+
major,count:= nums[0],0
59+
majorMap:=make(map[int]int)
60+
61+
for_,v:=range nums {
62+
majorMap[v]++
63+
}
64+
65+
fori,v:=range majorMap {
66+
if v > count {
67+
major = i
68+
count = v
69+
}
70+
}
71+
72+
return major
73+
}
74+
```
75+
76+
###思路3
77+
>先排序再循环判断每个数出现的次数
78+
79+
```go
80+
funcmajorityElement4(nums []int)int {
81+
//将原数组排序
82+
nums =InsertSort(nums)
83+
84+
major,count:= nums[0],0
85+
86+
for_,v:=range nums {
87+
if count ==0 {
88+
count++
89+
major = v
90+
}elseif major == v {
91+
count++
92+
}else {
93+
count--
94+
}
95+
}
96+
97+
return major
98+
}
99+
100+
// 插入排序(Insert Sort)
101+
funcInsertSort(arr []int) []int {
102+
vari,j,tmpint
103+
for i =1; i <len(arr); i++ {
104+
tmp = arr[i]
105+
for j = i; j >0 && arr[j-1] > tmp; j-- {
106+
arr[j] = arr[j-1]
107+
}
108+
arr[j] = tmp
109+
}
110+
return arr
111+
}
112+
```
113+
114+
###思路4
115+
>利用分治分方法，借鉴了LeetCode某个大佬的分治解法，设计的非常精妙。
116+
117+
118+
```go
119+
funcmajorityElement(nums []int)int {
120+
iflen(nums) ==1 {
121+
return nums[0]
122+
}
123+
n:=len(nums)
124+
125+
if n%2 ==1 {
126+
count:=1
127+
128+
fori:=0; i < n-1; i++ {
129+
if nums[n-1] == nums[i] {
130+
count++
131+
}
132+
}
133+
if count > n/2 {
134+
return nums[n-1]
135+
}
136+
}
137+
numsTmp:= []int{}
138+
139+
fori:=0; i < n/2; i++ {
140+
if nums[2*i] == nums[2*i+1] {
141+
numsTmp =append(numsTmp, nums[2*i])
142+
}
143+
}
144+
145+
returnmajorityElement(numsTmp)
146+
}
147+
```
148+
149+
150+
##结语
151+
152+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
153+
154+
[title]:hthttps://leetcode.com/problems/majority-element/
155+
[me]:https://github.com/kylesliu/awesome-golang-leetcode

‎src/0169.Majority-Element/Solution.go

Lines changed: 122 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,122 @@
1+
package Solution
2+
3+
//解法1： 循环计数，代码比较简单，LeetCode上的Case都是有Majority的，所以这里确实很多判断
4+
funcmajorityElement1(nums []int)int {
5+
major,count:=nums[0],0
6+
7+
for_,v:=rangenums {
8+
ifcount==0 {
9+
count++
10+
major=v
11+
}elseifmajor==v {
12+
count++
13+
}else {
14+
count--
15+
}
16+
}
17+
18+
returnmajor
19+
}
20+
21+
//解法2: 2次循环
22+
funcmajorityElement2(nums []int)int {
23+
major,count:=nums[0],0
24+
25+
for_,v1:=rangenums {
26+
tmpCount:=0
27+
for_,v2:=rangenums {
28+
ifv2==v1 {
29+
tmpCount++
30+
}
31+
}
32+
iftmpCount>count {
33+
count=tmpCount
34+
major=v1
35+
}
36+
}
37+
38+
returnmajor
39+
}
40+
41+
//解法3: Map
42+
funcmajorityElement3(nums []int)int {
43+
major,count:=nums[0],0
44+
majorMap:=make(map[int]int)
45+
46+
for_,v:=rangenums {
47+
majorMap[v]++
48+
}
49+
50+
fori,v:=rangemajorMap {
51+
ifv>count {
52+
major=i
53+
count=v
54+
}
55+
}
56+
57+
returnmajor
58+
}
59+
60+
//解法4: 先排序再依次比对
61+
funcmajorityElement4(nums []int)int {
62+
//将原数组排序
63+
nums=InsertSort(nums)
64+
65+
major,count:=nums[0],0
66+
67+
for_,v:=rangenums {
68+
ifcount==0 {
69+
count++
70+
major=v
71+
}elseifmajor==v {
72+
count++
73+
}else {
74+
count--
75+
}
76+
}
77+
78+
returnmajor
79+
}
80+
81+
// 插入排序(Insert Sort)
82+
funcInsertSort(arr []int) []int {
83+
vari,j,tmpint
84+
fori=1;i<len(arr);i++ {
85+
tmp=arr[i]
86+
forj=i;j>0&&arr[j-1]>tmp;j-- {
87+
arr[j]=arr[j-1]
88+
}
89+
arr[j]=tmp
90+
}
91+
returnarr
92+
}
93+
94+
//解法5: 分治算法
95+
funcmajorityElement5(nums []int)int {
96+
iflen(nums)==1 {
97+
returnnums[0]
98+
}
99+
n:=len(nums)
100+
101+
ifn%2==1 {
102+
count:=1
103+
104+
fori:=0;i<n-1;i++ {
105+
ifnums[n-1]==nums[i] {
106+
count++
107+
}
108+
}
109+
ifcount>n/2 {
110+
returnnums[n-1]
111+
}
112+
}
113+
numsTmp:= []int{}
114+
115+
fori:=0;i<n/2;i++ {
116+
ifnums[2*i]==nums[2*i+1] {
117+
numsTmp=append(numsTmp,nums[2*i])
118+
}
119+
}
120+
121+
returnmajorityElement1(numsTmp)
122+
}

0 commit comments

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