jean.timex
BAN USERThe idea is to use a hashmap to help get the index of the target value in B. Each time when A[i] is not equal to B[i], we must need to swap, if A[i] is already 0, then we just need to swap 0 and B[i] in A, otherwise, use 0 to help. The solution should be O(n).
public void solve(int[] A, int[] B, int n) {
// use a map to track the index of a value
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < n; i++) {
map.put(A[i], i);
}
for (int i = 0; i < n; i++) {
if (A[i] != B[i]) {
if (A[i] != 0) {
swap(A, i, map.get(0), map);
}
swap(A, i, map.get(B[i]), map);
}
}
}
void swap(int[] A, int i, int j, Map<Integer, Integer> map) {
System.out.format("%d <-> %d\n", A[i], A[j]);
map.put(A[i], j);
map.put(A[j], i);
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
public List<String> solve(String input) {
List<String> res = new ArrayList<String>();
int n = input.length();
for (int i = 1; i < n - 1; i++) {
for (int j = n - 1; j > i; j--) {
String s = input.substring(0, i) + String.valueOf(j - i) + input.substring(j);
res.add(s);
}
}
return res;
}
Sort and then binary search, O(nlogn)
Double[] findMaxRange(Double[] a) {
// step 1. sort the array
Arrays.sort(a, Collections.reverseOrder());
Double from = 0.0, to = 0.0;
int max = 0;
// step 2. for every element x, find the upper bound of x - 1
// upper bound here means the largest number >= x - 1
for (int i = 0; i < a.length; i++) {
int j = upper(a, 0, a.length - 1, a[i] - 1);
if (j - i + 1 > max) {
from = a[i];
to = a[i] - 1;
max = j - i + 1;
}
}
return new Double[]{from, to};
}
int upper(Double[] a, int lo, int hi, Double target) {
int mid = lo + (hi - lo) / 2;
if (a[mid] >= target && (mid == a.length - 1 || a[mid + 1] < target)) {
return mid;
}
if (a[mid] < target) {
return upper(a, lo, mid - 1, target);
} else {
return upper(a, mid + 1, hi, target);
}
}
- jean.timex July 30, 2015We can solve this problem with reverse merge sort.
public static class Solution {
int max;
Map<Integer, Integer> map;
int getSurpasser(int[] nums) {
max = 0;
map = new HashMap<Integer, Integer>();
mergeSort(nums, 0, nums.length - 1);
return max;
}
void mergeSort(int[] a, int lo, int hi) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
mergeSort(a, lo, mid);
mergeSort(a, mid + 1, hi);
reverseMerge(a, lo, mid, hi);
}
void reverseMerge(int[] a, int lo, int mid, int hi) {
if (lo >= hi)
return;
// make a copy of a[]
int[] c = new int[a.length];
System.arraycopy(a, 0, c, 0, a.length);
// reverse merge
for (int k = hi, i = mid, j = hi; k >= lo; k--) {
if (i < lo) a[k] = c[j--];
else if (j < mid + 1) a[k] = c[i--];
else if (c[i] >= c[j]) a[k] = c[j--];
else {
// We need to avoid duplicates
if (i == mid || c[i] != c[i + 1]) {
int count = map.containsKey(c[i]) ? map.get(c[i]) : 0;
count += j - mid;
map.put(c[i], count);
max = Math.max(max, count);
}
a[k] = c[i--];
}
}
}
}
Here is my solution using bit manipulation:
public int findNumber(int[] nums) {
int ones = 0, twos = 0, threes = 0;
for (int i = 0; i < nums.length; i++) {
int x = nums[i];
twos |= ones & x;
ones ^= x;
threes = ones & twos;
ones &= ~threes;
twos &= ~threes;
}
return ones | twos;
}
ones holds the numbers that appear once, twos holds the number that appear twice, threes holds the numbers that appear three times.
- jean.timex July 28, 2015
O(n) Time and space complexity solution:
- jean.timex September 08, 2015