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