Array
Last Updated: 2022-02-12
MaxDiff
Given an array, find the max diff between one integer and the integers to its right. e.g. [1, 5, 3, 65, 7, 43]
, the max
is 65 - 7 = 58
.
int maxdiff(int *a, int len)
{
int m = a[0];
int mdiff = 0x80000000;
int i;
for (i = 1; i < len; i++) {
if (m - a[i] > mdiff) {
mdiff = m - a[i];
}
if (a[i] > m) {
m = a[i];
}
}
return mdiff;
}
Binary Search
public class BinarySearch {
public static int rank(int key, int[] a) {
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (key < a[mid])
hi = mid - 1;
else if (key > a[mid])
lo = mid + 1;
else
return mid;
}
return -1;
}
public static void main(String[] args) {
int[] a = {1,2,3,4,5,6};
System.out.println(rank(5,a));
}
}
Shuffle
public static void shuffle(int[] a) {
for (int i = 0; i < a.length; i++){
int k = (int) (Math.random() * (a.length - i)) + i;
int tmp = a[k];
a[k] = a[i];
a[i] = tmp;
}
}
Find Peak In 2D Array
Find any peak in a 2D integer array.
1 3 6 4 2 4
5 9 3 5 1 3
2 6 3 7 9 3
3 4 7 2 7 2
Solution 1: Naive Search
Search every position until a peak is found. O(n^2)
.
Solution 2: Binary Search Rows
Take the middle 3 rows, find the maximum of each row (3 * O(n)
), drop the lower side half. Since the maximum of one row is larger than the other, it is guaranteed to be larger than any number in the other row. O(n log n)
.
Solution 3: Binary Search Alternating Rows and Columns
Similar to solution 2, but alternating between rows and columns, so first half of the rows are dropped, then half of the columns, then half of the rows.
O(N) + O(N/2) + O(N/4) + ... = O(N)