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<Integer> 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<Integer> LIS(int[] a) {

LinkedList<Integer> trackLargestIndex = new LinkedList<Integer>();

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<Integer> lis = new ArrayList<Integer>();

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--;

}

}