|
2 | 2 |
|
3 | 3 | classRerange { |
4 | 4 | publicstaticvoidmain(String[]strs) { |
5 | | -//int A[] = {1,2,3,4,-1, 2, 5, 5, -5, 6, -7,-8,843,6,1}; |
6 | | -intA[] = {1,2,-3,-4,-1, -2, -5, -5, -5,6, -7,-8,843,6,1}; |
| 5 | +intA[] = {1,2,3,4,-1,2,5,5, -5,6, -7,-8,843,6,1}; |
| 6 | +//int A[] = {1,2,-3,-4,-1, -2, -5, -5, -5, 6, -7,-8,843,6,1}; |
7 | 7 | rerange(A); |
8 | 8 |
|
9 | 9 | for (inti =0;i <A.length;i++) { |
@@ -99,7 +99,7 @@ public static void swap(int[] A, int n1, int n2) { |
99 | 99 | /* |
100 | 100 | Solution 2: |
101 | 101 | */ |
102 | | -publicstaticint[]rerange(int[]A) { |
| 102 | +publicstaticint[]rerange2(int[]A) { |
103 | 103 | // write your code here |
104 | 104 |
|
105 | 105 | // Check the input parameter. |
@@ -193,4 +193,75 @@ public static int[] rerange(int[] A) { |
193 | 193 |
|
194 | 194 | returnA; |
195 | 195 | } |
| 196 | + |
| 197 | +/* |
| 198 | + Solution 3: |
| 199 | + */ |
| 200 | +publicstaticint[]rerange(int[]A) { |
| 201 | +// write your code here |
| 202 | + |
| 203 | +// Check the input parameter. |
| 204 | +if (A ==null ||A.length <=2) { |
| 205 | +returnA; |
| 206 | + } |
| 207 | + |
| 208 | +intlen =A.length; |
| 209 | + |
| 210 | +intcntPositive =0; |
| 211 | + |
| 212 | +// store the positive numbers index. |
| 213 | +inti1 =0; |
| 214 | + |
| 215 | +for (inti2 =0;i2 <len;i2++) { |
| 216 | +if (A[i2] >0) { |
| 217 | +cntPositive++; |
| 218 | + |
| 219 | +// Put all the positive numbers at in the left part. |
| 220 | +swap(A,i1++,i2); |
| 221 | + } |
| 222 | + } |
| 223 | + |
| 224 | +// If positive numbers are more than negative numbers, |
| 225 | +// Put the positive numbers at first. |
| 226 | +intposPointer =1; |
| 227 | +intnegPointer =0; |
| 228 | + |
| 229 | +if (cntPositive >A.length /2) { |
| 230 | +// Have more Positive numbers; |
| 231 | +posPointer =0; |
| 232 | +negPointer =1; |
| 233 | + |
| 234 | +// Reverse the array. |
| 235 | +intleft =0; |
| 236 | +intright =len -1; |
| 237 | +while (left <right) { |
| 238 | +inttmp =A[left]; |
| 239 | +A[left] =A[right]; |
| 240 | +A[right] =tmp; |
| 241 | +left++; |
| 242 | +right--; |
| 243 | + } |
| 244 | + } |
| 245 | + |
| 246 | +// Reorder the negative and the positive numbers. |
| 247 | +while (true) { |
| 248 | +// Should move if it is in the range. |
| 249 | +while (posPointer <len &&A[posPointer] >0) { |
| 250 | +posPointer +=2; |
| 251 | + } |
| 252 | + |
| 253 | +// Should move if it is in the range. |
| 254 | +while (negPointer <len &&A[negPointer] <0) { |
| 255 | +negPointer +=2; |
| 256 | + } |
| 257 | + |
| 258 | +if (posPointer >=len ||negPointer >=len) { |
| 259 | +break; |
| 260 | + } |
| 261 | + |
| 262 | +swap(A,posPointer,negPointer); |
| 263 | + } |
| 264 | + |
| 265 | +returnA; |
| 266 | + } |
196 | 267 | } |