GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — Algorithm-Implementations/PairNumbersTotal.java at master · devForTheFuture/Algorithm-Implementations Expand file tree/ Copy pathPairNumbersTotal.javaMore file actions 73 lines (56 loc) · 1.43 KB / Copy pathPairNumbersTotal.javaFile metadata and controls73 lines (56 loc) · 1.43 KB 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 package algorithms; /** * Given an array of randomly sorted integers and an integer k, write a function which returns boolean True * if a pair of numbers exists in the array such that A[i] + A[j] = k and False otherwise. * Provide an O(N) and an O(N log N) solution. * * @author joeytawadrous */ public class PairNumbersTotal { public static void main (String[] args) { int[] array = {1,2,3}; System.out.println(IsExistsPairThatThierSumIsK2(array, 3)); } /* * O(N log N) */ static boolean IsExistsPairThatThierSumIsK(int[] array, int k) { for (int i = 0; i < array.length; i++) { int j = FindLeftmost(array, k - array[i]); if (j == -1) continue; if (i != j || (i + 1 < array.length && array[i] == array[i + 1])) return true; } return false; } static int FindLeftmost(int[] array, int k) { int l = 0; int r = array.length - 1; while (l < r) { int m = l + (r - l) / 2; if (array[m] >= k) r = m; else l = m + 1; } return array[l] == k ? l : -1; } /* * O(N) */ static boolean IsExistsPairThatThierSumIsK2(int[] array, int k) { int l = 0; int r = array.length - 1; while (l < r) { if (array[l] + array[r] == k) return true; else if (array[l] + array[r] > k) r--; else l++; } return false; } } |
| You are visitor 01402503 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |