Skip to content

Commit a747667

Browse files
Korben-CHYKorben-CHY
committed
implement ArrayUitl by Korben
1 parent 2808a2a commit a747667

File tree

3 files changed

+446
-0
lines changed

3 files changed

+446
-0
lines changed

‎group20/1107837739/1107837739Learning/lib/fastjson-1.2.7.jar

407 KB
Binary file not shown.

‎group20/1107837739/1107837739Learning/src/org/korben/coderising/array/ArrayUtil.java

Lines changed: 261 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,261 @@
1+
package org.korben.coderising.array;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
6+
/**
7+
* ArrayUtil
8+
*
9+
* Created by Korben on 26/02/2017.
10+
*/
11+
public class ArrayUtil {
12+
13+
/**
14+
* 给定一个整形数组a , 对该数组的值进行置换
15+
* 例如： a = [7, 9 , 30, 3] , 置换后为 [3, 30, 9,7]
16+
* 如果 a = [7, 9, 30, 3, 4] , 置换后为 [4,3, 30 , 9,7]
17+
*/
18+
public static void reverseArray(int[] origin) {
19+
ensureNotNull(origin);
20+
21+
int length = origin.length;
22+
for (int i = 0; i < length; i++) {
23+
if (i < length / 2) {
24+
int tmp = origin[i];
25+
origin[i] = origin[length - i - 1];
26+
origin[length - i - 1] = tmp;
27+
}
28+
}
29+
}
30+
31+
/**
32+
* 现在有如下的一个数组： int oldArr[]={1,3,4,5,0,0,6,6,0,5,4,7,6,7,0,5}
33+
* 要求将以上数组中值为0的项去掉，将不为0的值存入一个新的数组，生成的新数组为：
34+
* {1,3,4,5,6,6,5,4,7,6,7,5}
35+
*/
36+
37+
public static int[] removeZero(int[] oldArray) {
38+
ensureNotNull(oldArray);
39+
40+
int nonZeroCount = 0;
41+
for (int i : oldArray) {
42+
if (i != 0) {
43+
nonZeroCount++;
44+
}
45+
}
46+
47+
int newArr[] = new int[nonZeroCount];
48+
int newArrIndex = 0;
49+
for (int i : oldArray) {
50+
if (i != 0) {
51+
newArr[newArrIndex++] = i;
52+
}
53+
}
54+
55+
return newArr;
56+
}
57+
58+
/**
59+
* 给定两个已经排序好的整形数组， a1和a2 , 创建一个新的数组a3, 使得a3 包含a1和a2 的所有元素， 并且仍然是有序的
60+
* 例如 a1 = [3, 5, 7,8] a2 = [4, 5, 6,7] 则 a3 为[3,4,5,6,7,8] , 注意： 已经消除了重复
61+
*/
62+
public static int[] merge(int[] array1, int[] array2) {
63+
ensureNotNull(array1);
64+
ensureNotNull(array2);
65+
66+
int maxArraySize = array1.length + array2.length;
67+
int[] mergedArray = new int[maxArraySize];
68+
69+
int index1 = 0;
70+
int index2 = 0;
71+
int mergedIndex = -1;
72+
for (int i = 0; i < maxArraySize; i++) {
73+
if (index1 == array1.length) {
74+
System.arraycopy(array2, index2, mergedArray, mergedIndex + 1, array2.length - index2);
75+
mergedIndex += array2.length - index2;
76+
break;
77+
} else if (index2 == array2.length) {
78+
System.arraycopy(array1, index1, mergedArray, mergedIndex + 1, array1.length - index1);
79+
mergedIndex += array1.length - index1;
80+
break;
81+
} else {
82+
int compare = Integer.compare(array1[index1], array2[index2]);
83+
if (compare < 0) {
84+
mergedArray[++mergedIndex] = array1[index1++];
85+
} else if (compare > 0) {
86+
mergedArray[++mergedIndex] = array2[index2++];
87+
} else {
88+
mergedArray[++mergedIndex] = array1[index1++];
89+
index2++;
90+
}
91+
}
92+
}
93+
94+
// 清除数组多余部分
95+
if (mergedIndex + 1 < maxArraySize) {
96+
int[] resultArray = new int[mergedIndex + 1];
97+
System.arraycopy(mergedArray, 0, resultArray, 0, mergedIndex + 1);
98+
return resultArray;
99+
}
100+
101+
return mergedArray;
102+
}
103+
104+
/**
105+
* 把一个已经存满数据的数组 oldArray的容量进行扩展， 扩展后的新数据大小为oldArray.length + size
106+
* 注意，老数组的元素在新数组中需要保持
107+
* 例如 oldArray = [2,3,6] , size = 3,则返回的新数组为
108+
* [2,3,6,0,0,0]
109+
*/
110+
public static int[] grow(int[] oldArray, int size) {
111+
ensureNotNull(oldArray);
112+
113+
if (size < 0) {
114+
throw new IllegalArgumentException("size must > 0");
115+
}
116+
117+
int[] newArray = new int[oldArray.length + size];
118+
119+
System.arraycopy(oldArray, 0, newArray, 0, oldArray.length);
120+
for (int i = oldArray.length; i < newArray.length; i++) {
121+
newArray[i] = 0;
122+
}
123+
124+
return newArray;
125+
}
126+
127+
/**
128+
* 斐波那契数列为：1，1，2，3，5，8，13，21...... ，给定一个最大值， 返回小于该值的数列
129+
* 例如， max = 15 , 则返回的数组应该为 [1，1，2，3，5，8，13]
130+
* max = 1, 则返回空数组 []
131+
*/
132+
public static int[] fibonacci(int max) {
133+
if (max == 1) {
134+
int[] array = new int[1];
135+
array[1] = 1;
136+
return array;
137+
}
138+
139+
List<Integer> list = new ArrayList<>();
140+
141+
for (int i = 1; ; i++) {
142+
int fibonacciNumber = getFibonacciNumber(i);
143+
if (fibonacciNumber <= max) {
144+
list.add(fibonacciNumber);
145+
} else {
146+
break;
147+
}
148+
}
149+
150+
return list2Array(list);
151+
}
152+
153+
private static int getFibonacciNumber(int index) {
154+
if (index == 1) {
155+
return 1;
156+
}
157+
if (index == 2) {
158+
return 1;
159+
}
160+
return getFibonacciNumber(index - 2) + getFibonacciNumber(index - 1);
161+
}
162+
163+
/**
164+
* 返回小于给定最大值max的所有素数数组
165+
* 例如max = 23, 返回的数组为[2,3,5,7,11,13,17,19]
166+
*/
167+
public static int[] getPrimes(int max) {
168+
List<Integer> primeList = new ArrayList<>();
169+
if (max <= 1) {
170+
return new int[0];
171+
}
172+
173+
if (max >= 2) {
174+
primeList.add(2);
175+
}
176+
177+
// 所有偶数都不是素数, 所以这里采用 i += 2
178+
for (int i = 3; i < max; i += 2) {
179+
if (isPrimeNumber(i, primeList)) {
180+
primeList.add(i);
181+
}
182+
}
183+
184+
return list2Array(primeList);
185+
}
186+
187+
private static boolean isPrimeNumber(int number, List<Integer> primeList) {
188+
for (Integer prime : primeList) {
189+
if (number % prime == 0) {
190+
return false;
191+
}
192+
}
193+
return true;
194+
}
195+
196+
/**
197+
* 所谓“完数”， 是指这个数恰好等于它的因子之和，例如6=1+2+3
198+
* 给定一个最大值max， 返回一个数组， 数组中是小于max 的所有完数
199+
*/
200+
public static int[] getPerfectNumbers(int max) {
201+
if (max <= 1) {
202+
return new int[0];
203+
}
204+
205+
List<Integer> perfectNumberList = new ArrayList<>();
206+
for (int i = 2; i < max; i++) {
207+
if (isPerfectNumber(i)) {
208+
perfectNumberList.add(i);
209+
}
210+
}
211+
return list2Array(perfectNumberList);
212+
}
213+
214+
private static boolean isPerfectNumber(int number) {
215+
int sum = 1;
216+
for (int i = 2; i <= number / 2; i++) {
217+
if (number % i == 0) {
218+
sum += i;
219+
}
220+
}
221+
222+
return sum == number;
223+
}
224+
225+
/**
226+
* 用separator 把数组 array给连接起来
227+
* 例如array= [3,8,9], separator = "-"
228+
* 则返回值为"3-8-9"
229+
*/
230+
public static String join(int[] array, String separator) {
231+
ensureNotNull(array);
232+
233+
if (separator == null) {
234+
throw new NullPointerException();
235+
}
236+
237+
StringBuilder stringBuilder = new StringBuilder();
238+
for (int i = 0; i < array.length; i++) {
239+
stringBuilder.append(array[i]);
240+
if (i != array.length - 1) {
241+
stringBuilder.append(separator);
242+
}
243+
}
244+
245+
return stringBuilder.toString();
246+
}
247+
248+
private static int[] list2Array(List<Integer> list) {
249+
int[] result = new int[list.size()];
250+
for (int i = 0; i < list.size(); i++) {
251+
result[i] = list.get(i);
252+
}
253+
return result;
254+
}
255+
256+
private static void ensureNotNull(int[] array) {
257+
if (array == null) {
258+
throw new NullPointerException();
259+
}
260+
}
261+
}

0 commit comments

Comments
 (0)