juha
BAN USERThe algorithm is so simple. Calculate the sum and find the split point where both ends has the biggest difference.
int maxDiff(int[] nums) {
int total = 0;
for (int i = 0;i < nums.length;i++) {
total += nums[i];
}
int bestDiff = 0, subTotal = 0;
for (int i = 0;i < nums.length;i++) {
subTotal += nums[i];
// total = sub + remain
int diff = Math.abs(subTotal - total) + Math.abs(total - subTotal - total);
if (diff > bestDiff) {
bestDiff = diff;
}
}
return bestDiff;
}
If go through the lists taking the minimum number from each list gives the correct result. Probably there is room for optimization but the whole data set must be visited in any case.
class MinCommonRange {
static int[] minNums(int[][] rows) {
int bestMin = -1, bestMax = -1;
int[] rowIndexes = new int[rows.length];
while (true) {
int minRow = -1;
int min, max;
min = max = rows[0][rowIndexes[0]];
// Get min and max for current set
for (int i = 0;i < rows.length;i++) {
int[] row = rows[i];
int rowIndex = rowIndexes[i];
int num = row[rowIndex];
if (num <= min) {
// The lowest num which can be increased
if (rowIndex < row.length - 1) {
minRow = i;
}
min = num;
}
else if (num > max) {
max = num;
}
}
// The new best range
if (bestMin < 0 || bestMax - bestMin > max - min) {
bestMin = min;
bestMax = max;
}
// End of numbers
if (minRow < 0) {
break;
}
rowIndexes[minRow]++;
}
return new int[] { bestMin, bestMax };
}
public static void main(String[] args) {
int[] range = minNums(new int[][] {
new int[] { 4, 10, 15, 24, 26 },
new int[] { 0, 9, 12, 20 },
new int[] { 5, 18, 22, 30 }
});
System.out.println("Range: " + range[0] + " to " + range[1]);
}
}
A simple O(nm) solution that goes through the pixels "p" which with dimension w x h.
static void findLonelyPixels(int[] p, int w, int h) {
int rowPixels[] = new int[h];
int columnPixels[] = new int[w];
for (int x = 0;x < w;x++)
columnPixels[x] = -1;
int i = 0;
for (int y = 0;y < h;y++) {
rowPixels[y] = -1;
for (int x = 0;x < w;x++,i++) {
if (p[i] != 0) {
rowPixels[y] = rowPixels[y] < 0 ? x : -1;
columnPixels[x] = columnPixels[x] < 0 ? y : -1;
}
}
}
for (int y = 0;y < h;y++) {
int x = rowPixels[y];
if (x >= 0 && columnPixels[x] >= 0) {
System.out.println("Lonely pixel: " + x + "," + columnPixels[x]);
}
}
}
Using a sliding window the complexity is O(m + n). Expects that the char range is 0 - 255 so a hashmap could be better option.
- juha October 19, 2017