import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Collections; public class IntArrayOps { public static void main(String[] args) { int length = 10; int[] a = new int[length]; for (int i = 0; i < length; ++i) { a[i] = 0 + (int) (Math.random() * length); } System.out.println(Arrays.toString(a)); int[] a1 = new int[]{16, 18, 7, 8, 9, 10, 13, 0, 1, 2, 0, 9, 13, 14}; System.out.println(Arrays.toString(a1)); ArrayList lis = LIS(a1); System.out.println("LIS: " + lis.toString()); // a1 = new int[]{ 0, 1, 2, 0, 3,}; System.out.println(Arrays.toString(a1)); int max = LIS1(a1); System.out.println("LIS1: " + max); System.out.println("quick sort " + Arrays.toString(a1)); int[] a2 = a1.clone(); quickSort(a2, 0, a2.length - 1); System.out.println("quick sort result " + Arrays.toString(a2)); System.out.println("merge sort " + Arrays.toString(a1)); int[] a22 = a1.clone(); mergeSort(a22, 0, a22.length - 1); System.out.println("merge sort result " + Arrays.toString(a22)); // int pi = partition(a2, 0, 4); // System.out.println(pi); int rank = 9; int pick = pickRank(a1, 0, a1.length - 1, rank); System.out.println("a1 rank " + rank + " : " + pick); int a3 = 134; System.out.println(a3 + " reversed to " + isPalindrome1(a3)); int a4 = 1551; System.out.println(a4 + " isPalindrome: " + isPalindrome(a4)); int[] a5 = new int[]{3, -1, 1, 2, 4}; System.out.println(Arrays.toString(a5) + " 1st missing positiv: " + firstMissingPositive(a5, a5.length)); int[] a6 = new int[]{1, 3, 5, 0, 0, 0}; int[] a7 = new int[]{2, 4, 6}; mergeSorted(a6, a7); System.out.println("merge two sorted: " + Arrays.toString(a6)); int[] a8 = new int[]{1, 1, 1, 2, 2, 3, 4, 4, 5, 6, 6}; removeDupInplace(a8); System.out.println("remove dup of a sorted arr in place: " + Arrays.toString(a8)); int[] a9 = new int[]{-1, -1, 1, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8}; removeDupInplace2(a9); System.out.println("remove dup of a sorted arr in place2: " + Arrays.toString(a9)); int[] A = new int[]{1, 2, 4, 8, 9, 10}; int[] B = new int[]{11, 12, 13, 14}; System.out.println(Arrays.toString(A)); System.out.println(Arrays.toString(B)); System.out.println("find the k smallest element of A&B: " + findK(A, 0, A.length - 1, B, 0, B.length - 1, 5)); System.out.println("find the k smallest element of A&B1: " + findK1(A, B, 5)); if ((A.length + B.length) % 2 == 0) { int m1 = findK1(A, B, (A.length + B.length) / 2); int m2 = findK1(A, B, (A.length + B.length) / 2 + 1); System.out.println("find median: " + (double) (m1 + m2) / 2); } else { System.out.println("find median: " + findK1(A, B, (A.length + B.length) / 2 + 1)); } System.out.println("find median1: " + findMedianSortedArrays(A, B)); } public static double findMedianSortedArrays(int[] a, int[] b) { if (a.length > b.length) return findMedianSortedArrays(b, a, 0, b.length - 1); else return findMedianSortedArrays(a, b, 0, a.length - 1); } public static double findMedianSortedArrays(int[] a, int[] b, int la, int ra) { if (la > ra) return findMedianSortedArrays(b, a, Math.max(0, (a.length + b.length) / 2 - a.length), Math.min(b.length, (a.length + b.length) / 2)); int i = (ra + la) / 2; int j = (a.length + b.length) / 2 - i - 1; // i+j = meidan -1 if (j >= 0 && a[i] < b[j]) return findMedianSortedArrays(a, b, i + 1, ra); else if (j < b.length - 1 && a[i] > b[j + 1]) return findMedianSortedArrays(a, b, la, i - 1); if ((a.length + b.length) % 2 == 1) return (double) a[i]; else { if (i > 0) { if (j >= 0) return (double) (a[i] + Math.max(b[j], a[i - 1])) / 2; else return (double) (a[i] + a[i - 1]) / 2; } else return (double) (a[i] + b[j]) / 2; } } public static int findK1(int[] a, int[] b, int k) { if (k > (a.length + b.length) || k < 0) return -1; int i = (int) ((double) (a.length) / (a.length + b.length) * (k - 1)); int j = k - 1 - i; // i+j = k-1 int ai_1 = (i == 0) ? Integer.MIN_VALUE : a[i - 1]; int bj_1 = (j == 0) ? Integer.MIN_VALUE : b[j - 1]; int ai = (i == a.length) ? Integer.MAX_VALUE : a[i]; int bj = (j == b.length) ? Integer.MAX_VALUE : b[j]; if (bj_1 < ai && ai < bj) return ai; else if (ai_1 < bj && bj < ai) return bj; if (ai < bj_1) return findK1(Arrays.copyOfRange(a, i + 1, a.length), Arrays.copyOfRange(b, 0, j), k - i - 1); else // bj < ai_1 return findK1(Arrays.copyOfRange(a, 0, i), Arrays.copyOfRange(b, j + 1, b.length), k - j - 1); } // find the k smallest element of two sorted arrays public static int findK(int[] a, int la, int ra, int[] b, int lb, int rb, int k) { if (la < 0 || lb < 0 || ra > a.length - 1 || rb > b.length - 1 || k > (ra - la + 1 + rb - lb + 1) || k < 0) return -1; int i = (int) ((double) (ra - la + 1) / (ra - la + 1 + rb - lb + 1) * (k - 1)) + la; int j = k - 1 - (i - la) + lb; // i+j = k-1 int ai_1 = (i == 0) ? Integer.MIN_VALUE : a[i - 1]; int bj_1 = (j == 0) ? Integer.MIN_VALUE : b[j - 1]; int ai = (i == ra + 1) ? Integer.MAX_VALUE : a[i]; int bj = (j == rb + 1) ? Integer.MAX_VALUE : b[j]; if (bj_1 < ai && ai < bj) return ai; else if (ai_1 < bj && bj < ai) return bj; if (ai < bj_1) return findK(a, i + 1, ra, b, lb, j - 1, k - 1 - (i - la)); else // bj < ai_1 return findK(a, la, i - 1, b, j + 1, rb, k - 1 - (j - lb)); } public static void removeDupInplace2(int[] a) { if (a.length <= 1) return; int i = 0, j = 0; while (++i < a.length) { if (a[j] != a[i]) a[++j] = a[i]; } while (++j < a.length) a[j] = 0; } public static void removeDupInplace1(int[] a) { if (a.length <= 1) return; int i, j = 0; for (i = 1; i < a.length; ++i) { if (a[j] != a[i]) { a[j + 1] = a[i]; j++; } } j++; while (j < a.length) { a[j] = 0; j++; } } // not a good solution public static void removeDupInplace(int[] a) { if (a.length <= 1) return; for (int i = 1; i < a.length; ++i) { if (a[i] <= a[i - 1]) { int j = i + 1; while (j < a.length) { if (a[j] > a[i - 1]) { //int tmp = a[i]; a[i] = a[j]; //a[j] = tmp; break; } j++; if (j == a.length - 1) { while (i < a.length) { a[i] = 0; i++; } return; } } } if (a[i] == 0) return; } } public static void mergeSorted(int[] l, int[] s) { int space = 0, i = 0, j = -1, k = s.length - 1; while (i < l.length) { if (l[i] == 0) space++; else j++; // last non 0 int i++; } if (space < s.length) return; i = l.length - 1; while (k >= 0) { if (s[k] >= l[j]) { l[i--] = s[k--]; } else { l[i--] = l[j--]; } } while (k >= 0) { l[j--] = s[k--]; } } public static int firstMissingPositive(int A[], int n) { if (A.length == 0) return 1; //The key idea is to put every element in A such that A[i]=i+1 for (int i = 0; i < n; i++) { while (A[i] != i + 1 && A[i] > 0 && A[i] <= n && A[i] != A[A[i] - 1]) { int temp = A[i]; A[i] = A[temp - 1]; A[temp - 1] = temp; } } for (int i = 0; i < n; i++) { if (A[i] != i + 1) return i + 1; } return n + 1; } public static boolean isPalindrome(int x) { if (x < 0) return false; int div = 1; while (x / div >= 10) { div *= 10; } while (x != 0) { int l = x / div; int r = x % 10; if (l != r) return false; x = (x % div) / 10; div /= 100; } return true; } public static boolean isPalindrome1(int x) { if (x < 0) return false; return x == reverseInt(x); } public static int reverseInt(int a) { int r = 0; while (a != 0) { r = a % 10 + r * 10; a = a / 10; } return r; } // longest increasing sequence public static ArrayList LIS(int[] a) { LinkedList trackLargestIndex = new LinkedList(); int[] path = new int[a.length]; trackLargestIndex.add(0); path[0] = 0; for (int i = 1; i < a.length; ++i) { if (a[trackLargestIndex.getLast()] <= a[i]) { path[i] = trackLargestIndex.getLast(); // record the index of previous smaller element trackLargestIndex.add(i); // record the index of the largest element } else { int s, e; for (s = 0, e = trackLargestIndex.size() - 1; s < e; ) { int m = (e + s) / 2; if (a[trackLargestIndex.get(m)] <= a[i]) s = m + 1; else e = m; } if (a[i] < a[trackLargestIndex.get(s)]) { trackLargestIndex.set(s, i); if (s > 0) path[i] = trackLargestIndex.get(s - 1); else path[i] = 0; } } } int index = trackLargestIndex.getLast(); ArrayList lis = new ArrayList(); for (int n = 0; n < trackLargestIndex.size(); ++n) { lis.add(0, a[index]); index = path[index]; } return lis; } public static int LIS1(int[] a) { int max = 1; int[] trackTable = new int[a.length + 1]; // initial all 0 ; track index of the length of sequence trackTable[1] = 0; // 0 is the index of the smallest length 1. for (int i = 1; i < a.length; ++i) { if (a[i] < a[trackTable[1]]) trackTable[1] = i; else if (a[i] >= a[trackTable[max]]) { trackTable[max + 1] = i; max++; } else { // smallest < a[i] < largest int s = 1; int e = max; while (s < e) { int m = (e + s) / 2; if (a[trackTable[m]] <= a[i]) s = m + 1; else e = m; } trackTable[s] = i; } } return max; } public static int partition(int[] a, int left, int right) { int pivot = a[(left + right) / 2]; //a random pick while (left <= right) { while (a[right] > pivot) right--; while (a[left] < pivot) left++; if (left <= right) { int tmp = a[right]; a[right] = a[left]; a[left] = tmp; right--; left++; } } return left; } public static void quickSort(int[] a, int s, int e) { int pivot = partition(a, s, e); if (s < pivot - 1) quickSort(a, s, pivot - 1); if (pivot < e) quickSort(a, pivot, e); } public static int max(int[] array, int left, int right) { int max = Integer.MIN_VALUE; for (int i = left; i <= right; i++) { max = Math.max(array[i], max); } return max; } public static int pickRank(int[] a, int left, int right, int rank) { int pivotIndex = partition(a, left, right); int leftSize = pivotIndex - left; if (leftSize == rank) return max(a, left, pivotIndex); else if (rank < leftSize) { return pickRank(a, left, pivotIndex - 1, rank); } else //(rank > leftSize) return pickRank(a, pivotIndex, right, rank - leftSize); } public static void mergeSort(int[] a, int s, int e) { if (s < e) { int m = (s + e) / 2; mergeSort(a, s, m); mergeSort(a, m + 1, e); merge(a, s, m, e); } } public static void merge(int[] a, int left, int middle, int right) { int[] helper = new int[a.length]; for (int i = left; i <= right; ++i) { helper[i] = a[i]; } int helperRight = right; int helperMiddle = middle; int current = right; while (helperMiddle >= left && helperRight > middle) { if (helper[helperRight] > helper[helperMiddle]) { a[current] = helper[helperRight]; helperRight--; current--; } else { a[current] = helper[helperMiddle]; helperMiddle--; current--; } } while (helperRight > middle) { a[current] = helper[helperRight]; current--; helperRight--; } } }