Maxim
BAN USERQuite long solution using tree with cached size of the right subtree for each node. Complexity: time O(n log n), space: O(n)
public int getMaxSupessor(int[] array) {
Tree tree = new Tree();
int maxSupessor = Integer.MIN_VALUE;
for(int i=array.length-1; i>=0; i--) {
tree.add(array[i]);
maxSupessor = Math.max(maxSupessor, tree.getSupessor(array[i]));
}
return maxSupessor;
}
public class Tree {
private Node root;
public void add(int value) {
if (root == null)
root = new Node(value);
add(value, root);
}
private void add(int value, Node node) {
if (value == node.value) {
node.count++;
return;
}
if (value < node.value) {
if (node.left == null)
node.left = new Node(value);
else
add(value, node.left);
} else {
node.rightSize++;
if (node.right == null)
node.right = new Node(value);
else
add(value, node.right);
}
}
public int getSupessor(int value) {
return getSupessor(value, root);
}
private int getSupessor(int value, Node node) {
if (node == null)
return 0;
if (value < node.value)
return node.count + node.rightSize + getSupessor(value, node.left);
if (node.value < value)
return getSupessor(value, node.right);
return node.rightSize;
}
}
public class Node {
public int value;
public Node left;
public Node right;
public int count;
public int rightSize;
public Node(int value) {
count = 1;
rightSize = 0;
this.value = value;
}
}
It's just greedy algorithm, and it works:
public static String getCompressedString(String source){
int[] usedChars = new int[256];
for(int i='a'; i<='z'; i++){
usedChars[i]=0;
}
for(int i=0; i<source.length(); i++){
usedChars[source.charAt(i)]++;
}
for(int i='z'; i>='a'; i--){
if(usedChars[i]>0){
String[] strings = getAllVariants(source, (char)i, usedChars[i]);
source = getMinString(strings);
}
}
return source;
}
private static String getMinString(String[] strings){
String result = strings[0];
for(int i=1; i<strings.length; i++){
if(strings[i].compareTo(result) < 0)
result = strings[i];
}
return result;
}
private static String[] getAllVariants(String source, char c, int charsCount){
String[] result = new String[charsCount];
for(int i=0; i<charsCount; i++){
result[i]="";
}
int index=0;
for(int i=0; i<source.length(); i++){
for(int j=0; j<charsCount; j++){
if(source.charAt(i)!=c){
result[j]+=source.charAt(i);
}else{
if(j==index)
result[j]+=c;
}
}
if(source.charAt(i)==c)
index++;
}
return result;
}
O(n), O(n) solution:
public static void reorder(int[] array){
int totalNegativ=0;
for(int i=0; i < array.length; i++){
if(array[i] < 0)
totalNegativ++;
}
int[] positions = new int[array.length];
int negativLeft = totalNegativ;
int positivMeet = 0;
for(int i=0; i < array.length; i++){
if(array[i] < 0){
positions[i] = i - positivMeet;
negativLeft--;
}else{
positions[i] = i + negativLeft;
positivMeet++;
}
}
for(int i=0; i<array.length; i++){
while(positions[i]!=i){
swap(array, positions, i, positions[i]);
}
}
}
private static void swap(int[] array, int[] positions, int i, int j){
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
tmp = positions[i];
positions[i] = positions[j];
positions[j] = tmp;
}
Here is my solution on JavaScript. Algorythm is following: go throw all values from min to max, assume it's the left border of the range, and look for a right one. Store the best options and return it as a result;
function getSmallestRange(lines){
var k = lines.length;
var currentIndexes = [];
for(var i=0; i<k; i++)
{
currentIndexes[i]=0;
}
var minRangeSize=-1;
var minRangeLeft=0;
var minRangeRight=0;
var minLine;
while((minLine = getLineWithMinValue(lines, currentIndexes)) >= 0){
var rangeRight = getRangeRight(lines, currentIndexes);
var rangeLeft = lines[minLine][currentIndexes[minLine]];
rangeSize = rangeRight - rangeLeft;
if(minRangeSize < 0 || rangeSize < minRangeSize){
minRangeSize = rangeSize;
minRangeLeft = rangeLeft;
minRangeRight = rangeRight;
}
currentIndexes[minLine]++;
}
if(minRangeSize < 0)
return "not found";
return "["+minRangeLeft + ", " + minRangeRight+"]";
}
function getRangeRight(lines, currentIndexes){
var maxValue=0;
var maxIndex=-1;
for(var i=0; i<lines.length; i++){
if(currentIndexes[i] < lines[i].length){
var currentIndex = lines[i][currentIndexes[i]];
if(maxIndex<0 || currentIndex > maxValue){
maxValue = currentIndex;
maxIndex = i;
}
}
}
return maxValue;
}
function getLineWithMinValue(lines, currentIndexes){
var minIndex = -1;
var minValue = 0;
for(var i=0; i<lines.length; i++){
if(currentIndexes[i] >= lines[i].length)
return -1;
if(minIndex < 0 || lines[i][currentIndexes[i]] < minValue){
minIndex = i;
minValue = lines[i][currentIndexes[i]];
}
}
return minIndex;
}
Implemented this solution using PriorityQueue in Java:
- Maxim December 10, 2015