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

Commitfb5b707

Browse files
authored
Merge pull requestneetcode-gh#1441 from Mahim1997/dev/1985_Java_Swift
1985. Find the Kth Largest Integer in the Array
2 parentsfc52900 +3950604 commitfb5b707

File tree

2 files changed

+175
-0
lines changed

2 files changed

+175
-0
lines changed
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
// Min Heap comparator for reverse priority queue
2+
classStringNumberComparartorimplementsComparator<String> {
3+
@Override
4+
publicintcompare(Strings1,Strings2) {
5+
if(s1.length() !=s2.length()) {
6+
return (s1.length() -s2.length());
7+
}
8+
intlen =s1.length();
9+
for(inti=0;i<len;i++) {
10+
charc1 =s1.charAt(i),c2 =s2.charAt(i);
11+
if(c1 ==c2) {continue; }
12+
return (c1 -c2);
13+
}
14+
return0;
15+
}
16+
}
17+
18+
classSolution {
19+
publicStringkthLargestNumber(String[]nums,intk) {
20+
// Reverse pq to store only k elements [i.e. Min Heap]
21+
PriorityQueue<String>pq =newPriorityQueue<>(newStringNumberComparartor());
22+
23+
for(StringnumStr:nums) {
24+
pq.add(numStr);
25+
if(pq.size() >k) {
26+
pq.remove();
27+
}
28+
}
29+
30+
returnpq.peek();
31+
}
32+
}
Lines changed: 143 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,143 @@
1+
classSolution{
2+
func kthLargestNumber(_ nums:[String], _ k:Int)->String{
3+
// Use a Min Heap for storing upto k-elements max in the priority queue
4+
varheap:Heap<String>=Heap(sort:{(str1, str2)in
5+
guard str1.count== str2.countelse{return str1.count< str2.count}
6+
for(c1, c2)inzip(str1, str2){
7+
guard c1== c2else{return c1< c2}
8+
}
9+
returnfalse
10+
})
11+
12+
nums.forEach{ numin
13+
heap.insert(num)
14+
if heap.count> k{
15+
heap.remove()
16+
}
17+
}
18+
19+
return heap.peek()??""
20+
}
21+
}
22+
23+
// Heap used from https://github.com/kodecocodes/swift-algorithm-club/blob/master/Heap/Heap.swift
24+
publicstructHeap<T>{
25+
varnodes=[T]()
26+
27+
privatevarorderCriteria:(T,T)->Bool
28+
29+
publicinit(sort:@escaping(T,T)->Bool){
30+
self.orderCriteria= sort
31+
}
32+
33+
publicinit(array:[T], sort:@escaping(T,T)->Bool){
34+
self.orderCriteria= sort
35+
configureHeap(from: array)
36+
}
37+
38+
privatemutatingfunc configureHeap(from array:[T]){
39+
nodes= array
40+
foriinstride(from:(nodes.count/2-1), through:0, by:-1){
41+
shiftDown(i)
42+
}
43+
}
44+
45+
publicvarisEmpty:Bool{
46+
return nodes.isEmpty
47+
}
48+
49+
publicvarcount:Int{
50+
return nodes.count
51+
}
52+
53+
@inline(__always)internalfunc parentIndex(ofIndex i:Int)->Int{
54+
return(i-1)/2
55+
}
56+
57+
@inline(__always)internalfunc leftChildIndex(ofIndex i:Int)->Int{
58+
return2*i+1
59+
}
60+
61+
@inline(__always)internalfunc rightChildIndex(ofIndex i:Int)->Int{
62+
return2*i+2
63+
}
64+
65+
publicfunc peek()->T?{
66+
return nodes.first
67+
}
68+
69+
publicmutatingfunc insert(_ value:T){
70+
nodes.append(value)
71+
shiftUp(nodes.count-1)
72+
}
73+
74+
publicmutatingfunc insert<S:Sequence>(_ sequence:S)where S.Iterator.Element==T{
75+
forvaluein sequence{
76+
insert(value)
77+
}
78+
}
79+
80+
publicmutatingfunc replace(index i:Int, value:T){
81+
guard i< nodes.countelse{return}
82+
remove(at: i)
83+
insert(value)
84+
}
85+
86+
@discardableResultpublicmutatingfunc remove()->T?{
87+
guard !nodes.isEmptyelse{returnnil}
88+
if nodes.count==1{
89+
return nodes.removeLast()
90+
}else{
91+
letvalue=nodes[0]
92+
nodes[0]= nodes.removeLast()
93+
shiftDown(0)
94+
return value
95+
}
96+
}
97+
98+
@discardableResultpublicmutatingfunc remove(at index:Int)->T?{
99+
guard index< nodes.countelse{returnnil}
100+
letsize= nodes.count-1
101+
if index!= size{
102+
nodes.swapAt(index, size)
103+
shiftDown(from: index, until: size)
104+
shiftUp(index)
105+
}
106+
return nodes.removeLast()
107+
}
108+
109+
internalmutatingfunc shiftUp(_ index:Int){
110+
varchildIndex= index
111+
letchild=nodes[childIndex]
112+
varparentIndex=self.parentIndex(ofIndex: childIndex)
113+
114+
while childIndex>0 &&orderCriteria(child,nodes[parentIndex]){
115+
nodes[childIndex]=nodes[parentIndex]
116+
childIndex= parentIndex
117+
parentIndex=self.parentIndex(ofIndex: childIndex)
118+
}
119+
120+
nodes[childIndex]= child
121+
}
122+
123+
internalmutatingfunc shiftDown(from index:Int, until endIndex:Int){
124+
letleftChildIndex=self.leftChildIndex(ofIndex: index)
125+
letrightChildIndex= leftChildIndex+1
126+
127+
varfirst= index
128+
if leftChildIndex< endIndex &&orderCriteria(nodes[leftChildIndex],nodes[first]){
129+
first= leftChildIndex
130+
}
131+
if rightChildIndex< endIndex &&orderCriteria(nodes[rightChildIndex],nodes[first]){
132+
first= rightChildIndex
133+
}
134+
if first== index{return}
135+
136+
nodes.swapAt(index, first)
137+
shiftDown(from: first, until: endIndex)
138+
}
139+
140+
internalmutatingfunc shiftDown(_ index:Int){
141+
shiftDown(from: index, until: nodes.count)
142+
}
143+
}

0 commit comments

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