-
Notifications
You must be signed in to change notification settings - Fork 5
Expand file tree
/
Copy pathArray3.java
More file actions
161 lines (152 loc) · 3.16 KB
/
Array3.java
File metadata and controls
161 lines (152 loc) · 3.16 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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
package array;
public class Array3 {
//获取数字第一次出现位置
public static int getFirst(int p[], int i, int start, int end) {
// TODO Auto-generated method stub
if (p == null) {
return -1;
}
if (start == end) {
if (p[start] == i) {
return start;
} else {
return -1;
}
}
int mid = (start + end) / 2;
if (p[mid] >= i) {
return getFirst(p, i, start, mid);
} else {
return getFirst(p, i, mid + 1, end);
}
}
//获取数字最后一次出现位置
public static int getLast(int p[], int i, int start, int end) {
// TODO Auto-generated method stub
if (p == null) {
return -1;
}
if (start == end - 1) {
if (p[start] == i) {
return start;
} else {
return -1;
}
}
int mid = (start + end) / 2;
if (p[mid] > i) {
return getLast(p, i, start, mid - 1);
} else {
return getLast(p, i, mid, end);
}
}
//某数字出现次数
public static int getNumberAppearTimes(int p[], int i) {
if (p == null) {
return -1;
}
int first = getFirst(p, i, 0, p.length - 1);
int last = getLast(p, i, 0, p.length - 1);
if (first == -1 || last == -1) {
return -1;
} else {
return last - first + 1;
}
}
//两个只出现一次的数字
public static void getTwoAppearOnce(int p[]) {
if (p == null) {
return;
}
int n = 0;
for (int i = 0; i < p.length; i++) {
n = p[i] ^ n;
}
int x = 0;
int y = 0;
int diffBit = n ^ (n & (n - 1));
for (int i = 0; i < p.length; i++) {
if ((p[i] & diffBit) == 0) {
x = x ^ p[i];
} else {
y = y ^ p[i];
}
}
System.out.print(x + ", " + y);
}
//递增数组，找到和为s的两个数
public static void findTwoNumberIsSumS(int p[], int s) {
if (p == null) {
return;
}
int start = 0;
int end = p.length - 1;
while (start != end) {
if (p[start] + p[end] == s) {
System.out.print(p[start] + " ");
System.out.print(p[end]);
break;
} else if (p[start] + p[end] > s) {
end--;
} else {
start++;
}
}
}
//和为sum的递增正数列
public static void getSerialNumberSumN(int sum) {
if (sum <= 2) {
return;
}
int start = 1;
int end = 2;
int mid = (start + sum) / 2;
int tsum = 3;
while (start < mid) {
if (tsum == sum) {
System.out.print(start + "~" + end + "\n");
} else if (tsum > sum) {
while (tsum > sum) {
tsum -= start;
start++;
}
continue;
}
end++;
tsum += end;
}
}
//最大最小值辅助类
public static class ValueHolder {
int maxNum;
int minNum;
}
//获取最大最小值
public static ValueHolder getMaxMinNumber(int p[], int start, int end) {
if (p == null) {
return null;
}
ValueHolder valueHolder = new ValueHolder();
if (start == end) {
valueHolder.maxNum = p[start];
valueHolder.minNum = p[start];
return valueHolder;
}
int mid = (start + end) / 2;
int lmax = getMaxMinNumber(p, start, mid).maxNum;
int lmin = getMaxMinNumber(p, start, mid).minNum;
int rmax = getMaxMinNumber(p, mid + 1, end).maxNum;
int rmin = getMaxMinNumber(p, mid + 1, end).minNum;
if (lmax > rmax) {
valueHolder.maxNum = lmax;
} else {
valueHolder.maxNum = rmax;
}
if (lmin < rmin) {
valueHolder.minNum = lmin;
} else {
valueHolder.minNum = rmin;
}
return valueHolder;
}
}