By using min
heap kind of structure we can find the minimum element efficiently. Following is
complete working example.
public class MinUtil { int getMin(int[] ele) { if (Objects.isNull(ele)) { throw new NullPointerException("Array shouldn't be null"); } if (ele.length == 0) { throw new IllegalArgumentException("Array shouldn't be empty"); } if (ele.length == 1) { return ele[0]; } int length = ele.length; for (int i = lastNonTerminalNode(ele); i >= 0; i--) { int left = leftIndex(i); int right = rightIndex(i); int tempIndex = i; if (ele[tempIndex] > ele[left]) { tempIndex = left; } if (right < length && ele[tempIndex] > ele[right]) { tempIndex = right; } if (tempIndex == i) continue; int temp = ele[tempIndex]; ele[tempIndex] = ele[i]; ele[i] = temp; } return ele[0]; } private int leftIndex(int i) { return 2 * i + 1; } private int rightIndex(int i) { return 2 * i + 2; } private int lastNonTerminalNode(int a[]) { int len = a.length; return (len / 2) - 1; } }
import static org.junit.Assert.assertEquals; import org.junit.Test; public class MinUtilTet { MinUtil obj = new MinUtil(); @Test public void test1() { assertEquals(obj.getMin(new int[] { 0 }), 0); assertEquals(obj.getMin(new int[] { 0, 1 }), 0); assertEquals(obj.getMin(new int[] { 1, 0 }), 0); assertEquals(obj.getMin(new int[] { 0, 1, 2 }), 0); assertEquals(obj.getMin(new int[] { 1, 0, 2 }), 0); assertEquals(obj.getMin(new int[] { 2, 1, 0 }), 0); assertEquals(obj.getMin(new int[] { 5, 4, 3, 2, 1, 0 }), 0); assertEquals(obj.getMin(new int[] { 5, 4, 3, 2, 1, 0, -1, -2, -3 }), -3); } @Test(expected = NullPointerException.class) public void test2() { obj.getMin(null); } @Test(expected = IllegalArgumentException.class) public void test3() { obj.getMin(new int[] {}); } }
No comments:
Post a Comment