数组0元素后置算法

完整算法实现

1 /** 2 * 将数组中0全部后置 eg: [1,2,0,3] --> [1,2,3,0] 3 * 4 * @author kangye 5 */ 6 public class MoveZerosInArray { 7 8 /** 9 * 冒泡实现 O(N^2) 10 */ 11 public void moveSorting(int[] array) { 12 validateArray(array); 13 14 boolean swap = true; 15 while (swap) { 16 swap = false; 17 for (int i = 0; i < array.length - 1; i++) { 18 if ((array[i] < array[i + 1] && array[i + 1] > 0)) { 19 swap(array, i, i + 1); 20 swap = true; 21 } 22 } 23 } 24 } 25 26 /** 27 * 优化， O(N) 28 */ 29 public void moveUsingTwoPointers(int[] array) { 30 validateArray(array); 31 32 int left = 0; 33 int right = array.length - 1; 34 while (left < right) { 35 if (array[left] == 0 && array[right] != 0) { 36 swap(array, left, right); 37 } 38 if (array[left] != 0) { 39 left++; 40 } 41 if (array[right] == 0) { 42 right--; 43 } 44 } 45 } 46 47 private void validateArray(int[] array) { 48 if (array == null) { 49 throw new IllegalArgumentException("You can't pass a null array as argument."); 50 } 51 } 52 53 private void swap(int[] array, int a, int b) { 54 int temp = array[a]; 55 array[a] = array[b]; 56 array[b] = temp; 57 } 58 }

补充一个单元测试,写法注意：

 1. 至于test目录下, 保持包名相同

 2. 类名和原测试类保持一致，增加Test后缀，方法名增加test

 3. 尽量使用junit原声断言，和异常申明（有时间补充一篇单元测试方法）

1 /** 2 * @author kangye 3 */ 4 public class MoveZerosInArrayTest { 5 6 private MoveZerosInArray moveZeros; 7 8 @Before 9 public void setUp() { 10 moveZeros = new MoveZerosInArray(); 11 } 12 13 @Test(expected = IllegalArgumentException.class) 14 public void shouldNotAcceptNullArraysSorting() { 15 moveZeros.moveSorting(null); 16 } 17 18 @Test 19 public void shouldWorkWithAnEmptyArraySorting() { 20 int[] array = new int[0]; 21 22 moveZeros.moveSorting(array); 23 24 assertArrayEquals(new int[0], array); 25 } 26 27 @Test 28 public void shouldOrganizeAnArrayFullOfZerosSorting() { 29 int[] array = { 0, 0, 0, 0, 0 }; 30 31 moveZeros.moveUsingTwoPointers(array); 32 33 int[] expected = { 0, 0, 0, 0, 0 }; 34 assertArrayEquals(expected, array); 35 } 36 37 @Test 38 public void shouldOrganizeAnArrayFullOfNonZerosSorting() { 39 int[] array = { 1, 1, 1, 1, 1 }; 40 41 moveZeros.moveUsingTwoPointers(array); 42 43 int[] expected = { 1, 1, 1, 1, 1 }; 44 assertArrayEquals(expected, array); 45 } 46 47 @Test 48 public void shouldOrganizeAnArrayWithZerosAndNonPositiveIntegersSorting() { 49 int[] array = { 1, 0, 2, 3, 0 }; 50 51 moveZeros.moveUsingTwoPointers(array); 52 53 assertZerosAtRight(array); 54 } 55 56 @Test 57 public void shouldOrganizeAnArrayWithZerosPositiveAndNegativeIntegersSorting() { 58 int[] array = { 1, 0, 2, -3, 0, 0, 0, 0, -1 }; 59 60 moveZeros.moveUsingTwoPointers(array); 61 62 assertZerosAtRight(array); 63 } 64 65 @Test(expected = IllegalArgumentException.class) 66 public void shouldNotAcceptNullArraysWithTwoPointers() { 67 moveZeros.moveUsingTwoPointers(null); 68 } 69 70 @Test 71 public void shouldWorkWithAnEmptyArrayWithTwoPointers() { 72 int[] array = new int[0]; 73 74 moveZeros.moveUsingTwoPointers(array); 75 76 assertArrayEquals(new int[0], array); 77 } 78 79 @Test 80 public void shouldOrganizeAnArrayFullOfZerosWithTwoPointers() { 81 int[] array = { 0, 0, 0, 0, 0 }; 82 83 moveZeros.moveUsingTwoPointers(array); 84 85 int[] expected = { 0, 0, 0, 0, 0 }; 86 assertArrayEquals(expected, array); 87 } 88 89 @Test 90 public void shouldOrganizeAnArrayFullOfNonZerosWithTwoPointers() { 91 int[] array = { 1, 1, 1, 1, 1 }; 92 93 moveZeros.moveUsingTwoPointers(array); 94 95 int[] expected = { 1, 1, 1, 1, 1 }; 96 assertArrayEquals(expected, array); 97 } 98 99 @Test 100 public void shouldOrganizeAnArrayWithZerosAndNonPositiveIntegersWithTwoPointers() { 101 int[] array = { 1, 0, 2, 3, 0 }; 102 103 moveZeros.moveUsingTwoPointers(array); 104 105 assertZerosAtRight(array); 106 } 107 108 @Test 109 public void shouldOrganizeAnArrayWithZerosPositiveAndNegativeIntegersWithTwoPointers() { 110 int[] array = { 1, 0, 2, -3, 0, 0, 0, 0, -1 }; 111 112 moveZeros.moveUsingTwoPointers(array); 113 114 assertZerosAtRight(array); 115 } 116 117 private void assertZerosAtRight(int[] array) { 118 boolean zeroFounded = false; 119 for (int i : array) { 120 if (zeroFounded) { 121 assertEquals(0, i); 122 } else if (i == 0) { 123 zeroFounded = true; 124 } 125 } 126 } 127 }

 

转载于:https://www.cnblogs.com/kangye1014/p/5038488.html

相关资源：各显卡算力对照表！