Repository navigation
Expand file tree
/
Copy pathMedianOfSorted.java
More file actions
104 lines (80 loc) · 1.58 KB
/
Copy pathMedianOfSorted.java
File metadata and controls
104 lines (80 loc) · 1.58 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
import java.util.Scanner;
public class MedianOfSorted
{
static void median(String a[],int x[])
{
for(int i = 0; i < a.length; i++)
{
if(a[i].equals("r"))
{
// if array empty - error
// else remove - if exists
}
else if(a[i].equals("a"))
{
// add and sort
}
}
}
public static void main( String args[] ){
Scanner in = new Scanner(System.in);
int N;
N = in.nextInt();
String s[] = new String[N];
int x[] = new int[N];
for(int i=0; i<N; i++){
s[i] = in.next();
x[i] = in.nextInt();
}
median(s,x);
}
public int[] sort(int[] a)
{
if(a.length == 1)
return a;
int[] l = new int[(a.length/2)];
int[] r = new int[(int) Math.ceil(((double)a.length)/2)];
for(int i = 0; i < a.length/2; i++)
l[i] = a[i];
for(int i = a.length/2; i < a.length; i++)
r[i - a.length/2] = a[i];
l = sort(l);
r = sort(r);
return merge(l,r);
}
public int[] merge(int[] a, int[] b)
{
int[] c = new int[a.length + b.length];
int aIndex = 0;
int bIndex = 0;
int cIndex = 0;
while((aIndex < a.length) && (bIndex < b.length))
{
if(a[aIndex] < b[bIndex])
{
c[cIndex] = a[aIndex];
aIndex++;
cIndex++;
}
else
{
c[cIndex] = b[bIndex];
bIndex++;
cIndex++;
}
}
while(bIndex < b.length)
{
c[cIndex] = b[bIndex];
bIndex++;
cIndex++;
}
while(aIndex < a.length)
{
c[cIndex] = a[aIndex];
aIndex++;
cIndex++;
}
return c;
}
}