Tewelde
BAN USERpublic String sort(int[] a)
{
String[] ret=new String[a.length];
for(int i=0;i<ret.length;i++)
ret[i]=new Integer(a[i]).toString();
Arrays.sort(ret,new Comparator<String>()
{
public int compare(String x,String y)
{
return (y+x).compareTo(x+y);
}
});
StringBuilder sb=new StringBuilder();
for(String s:ret)
{
sb.append(s);
}
return sb.toString();
}
This is a single pass O(n*m) where n is the lengths of the big string and m is the combined length of the small strings
import java.util.*;
public class MinStringSpan
{
static class SmallString
{
public SmallString(String t)
{
this.t=t;
}
public String t;
public int matchIndex=-1;
public LinkedList<Integer> indexes=new LinkedList<Integer>();
public void checkChar(int i,char ch)
{
if(t.length()==1)
{
if(t.charAt(i)==ch)
matchIndex=i;
return;
}
Iterator<Integer> it=indexes.iterator();
while(it.hasNext())
{
int ind=it.next();
if(t.charAt(i-ind)==ch)
{
if(i-ind==t.length()-1)
{
matchIndex=ind;
it.remove();
}
}
else
it.remove();
}
if(ch==t.charAt(0))
{
indexes.add(i);
}
}
}
static public String minSpan(String s,String t1,String t2,String t3)
{
ArrayList<SmallString> small=new ArrayList<SmallString>();
for(String t:new String[]{t1,t2,t3})
{
if(t.length()>0)
small.add(new SmallString(t));
}
int n=s.length();
int minIndex1=-1;
int minIndex2=-1;
for(int i=0;i<n;i++)
{
char ch=s.charAt(i);
boolean found=true;
int thisi1=-1;
int thisi2=-1;
for(SmallString ss:small)
{
ss.checkChar(i,ch);
if(ss.matchIndex==-1)
found=false;
else if(found)
{
int i1=ss.matchIndex;
int i2=ss.matchIndex+ss.t.length();
if(thisi1==-1 || i1<thisi1)
thisi1=i1;
if(thisi2==-1 || i2>thisi2)
thisi2=i2;
}
}
if(found)
{
if(minIndex1==-1 || (thisi2-thisi1<minIndex2-minIndex1))
{
minIndex1=thisi1;
minIndex2=thisi2;
}
}
}
if(minIndex1==-1)
return "";
return s.substring(minIndex1,minIndex2);
} public static void main(String [] args)
{
String x=MinStringSpan.minSpan("abbcdefbc","bc","fbc","ef");
System.out.println(x);
}
}
This is my solution. I build a Trie out of the dictionary and crack one character at a time.
import java.*;
import java.util.*;
import java.util.function.*;
class DictCracker
{
static class TrieNode
{
public HashMap<Character,TrieNode> childs=new HashMap<Character,TrieNode>();
}
static class DictTrie
{
public TrieNode root=new TrieNode();
public DictTrie(ArrayList<String> dict)
{
for(String w:dict)
addWord(root,w);
}
void addWord(TrieNode n,String w)
{
int l=w.length();
for(int i=0;i<l;i++)
{
char ch=w.charAt(i);
TrieNode chld=n.childs.get(ch);
if(chld==null)
{
chld=new TrieNode();
n.childs.put(ch,chld);
}
n=chld;
}
}
}
static String crack(ArrayList<String> dict,Function<String,Integer> machine)
{
DictTrie t=new DictTrie(dict);
TrieNode n=t.root;
boolean found;
String ret="";
do
{
found=false;
for(Map.Entry<Character,TrieNode> ch:n.childs.entrySet())
{
String test=ret+ch.getKey();
if(machine.apply(test)==test.length())
{
found=true;
n=ch.getValue();
ret=test;
break;
}
}
}while(found);
return ret;
}
public static void main(String[] args)
{
ArrayList<String> dict=new ArrayList<String>(Arrays.asList( new String[]{"ab","zc","zr"}));
String word="zr";
String c=crack(dict,new Function<String,Integer>()
{
public Integer apply(String test)
{
int wl=word.length();
int tl=test.length();
if(tl>wl)
return -1;
int i;
for(i=0;i<tl;i++)
{
if(test.charAt(i)!=word.charAt(i))
break;
}
return i;
}
});
System.out.format("word=%s%n",c);
}
}
Here is my O(m*log(n)*(log(n)+log(m)) solution, for m and n equal it will be n*log(n)*log(n)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Row
{
int[] a;
int N;
public Row(int[] a)
{
this.a = a;
this.N = a.Length;
}
public void split(int dx, out int nl, out int lmax, out int ng, out int rmin, out int ne)
{
int i1 = -1;
int i2 = N;
while (i1 + 1 < i2)
{
int m = (i1 + i2) / 2;
if (2 * a[m] >= dx)
i2 = m;
else
i1 = m;
}
nl = 2 * i2;
lmax = nl > 0 ? a[i1] : 0;
i1 = -1;
i2 = N;
while (i1 + 1 < i2)
{
int m = (i1 + i2) / 2;
if (2 * a[m] <= dx)
i1 = m;
else
i2 = m;
}
ng = 2 * (N - i2);
rmin = ng > 0 ? a[i2] : 0;
ne = 2 * N - nl - ng;
}
}
class Program
{
static int matMedianSort(int[][] a)
{
List<int> all = new List<int>();
foreach (int[] r in a)
all.AddRange(r);
all.Sort(delegate(int x, int y)
{
return x.CompareTo(y);
});
if (all.Count % 2 == 0)
return (all[all.Count / 2 - 1] + all[all.Count / 2]) / 2;
return all[all.Count / 2];
}
static int matMedian(int[][] a)
{
int M = a.Length;
if (M == 0)
throw new Exception("Invalid");
int N = a[0].Length;
if (N == 0)
throw new Exception("Invalid");
if (M == 1 && N == 1)
return a[0][0];
Row[] rows = new Row[M];
int min = 0;
int max = 0;
for (int i = 0; i < M; i++)
{
rows[i] = new Row(a[i]);
if (i == 0 || min > a[i][0])
min = a[i][0];
if (i == 0 || max < a[i][N - 1])
max = a[i][N - 1];
}
int twon = N * M * 2;
int n = N * M;
while (true)
{
int lmax = min;
int rmin = max;
int dmix = min + max;
int nl, ng, ne;
nl = ng = ne = 0;
foreach (Row r in rows)
{
int nli, ngi, lmaxi, rmini, nei;
r.split(dmix, out nli, out lmaxi, out ngi, out rmini, out nei);
if (nli > 0 && lmaxi > lmax)
lmax = lmaxi;
if (ngi > 0 && rmini < rmin)
rmin = rmini;
nl += nli;
ng += ngi;
ne += nei;
}
if (nl <= n && ng <= n)
{
if (nl < n || ng < n)
return dmix / 2;
return (lmax + rmin) / 2;
}
if (nl < ng)
min = rmin;
else
max = lmax;
}
}
static void Main(string[] args)
{
Random r = new Random();
int M = 4;
int N = M;
int[][] a = new int[M][];
a[0] = new int[] { 174, 178, 184, 192 };
a[1] = new int[] { 311, 319, 321, 329 };
a[2] = new int[] { 319, 319, 319, 324 };
a[3] = new int[] { 327, 329, 338, 344 };
Console.WriteLine("median={0}", matMedian(a));
}
}
My implementation uses a maximum of 104 integer to store the integer data
using System;
using System.Collections.Generic;
using System.Text;
class VBI : IComparable<VBI>
{
const ulong MAXDP1 = 0x100000000;
const uint MAXD = 0xFFFFFFFF;
const int MAXN = 104;
int sign = 0;
List<uint> data = new List<uint>();
public VBI()
{
}
public VBI(VBI v, int s)
{
this.sign = v.sign * s;
this.data.AddRange(v.data);
}
public int CompareTo(VBI x)
{
return CompareTo(x, true);
}
public int CompareTo(VBI x, bool considerSign)
{
if (x == null)
return 1;
int ret;
if (considerSign)
{
ret = this.sign.CompareTo(x.sign);
if (ret != 0)
return ret;
if (this.sign == 0)
return 0;
}
ret = this.data.Count.CompareTo(x.data.Count);
if (ret != 0)
return ret * x.sign;
for (int i = data.Count - 1; i >= 0; i--)
{
ret = this.data[i].CompareTo(x.data[i]);
if (ret != 0)
return ret * x.sign;
}
return 0;
}
public static VBI _add(VBI a, VBI b, int sign)
{
VBI c = new VBI();
if (a.data.Count < b.data.Count)
{
VBI t = a;
a = b;
b = t;
}
int na = a.data.Count;
int nb = b.data.Count;
bool carry = false;
for (int i = 0; i < nb; i++)
{
ulong dc = (ulong)a.data[i] + (ulong)b.data[i];
if (carry)
dc++;
if (dc > MAXD)
{
carry = true;
c.data.Add((uint)dc & MAXD);
}
else
{
carry = false;
c.data.Add((uint)dc);
}
}
for (int i = nb; i < na; i++)
{
if (carry)
{
ulong dc = (ulong)a.data[i] + (ulong)1;
if (dc > MAXD)
c.data.Add((uint)(dc & MAXD));
else
{
carry = false;
c.data.Add((uint)dc);
}
}
else
c.data.Add(a.data[i]);
}
if (carry)
{
if (c.data.Count == MAXN)
throw new Exception(sign == 1 ? "Overflow" : "Underflow");
c.data.Add(1);
}
c.sign = sign;
return c;
}
public static VBI _sub(VBI a, VBI b, int sign)
{
VBI c = new VBI();
switch (a.CompareTo(b, false))
{
case 0:
return c;
case -1:
VBI t = a;
a = b;
b = t;
sign = -sign;
break;
}
int na = a.data.Count;
int nb = b.data.Count;
bool carry = false;
int zs = -1;
for (int i = 0; i < nb; i++)
{
ulong dc;
ulong da = a.data[i];
ulong db = b.data[i];
if (carry) db++;
if (da >= db)
{
carry = false;
dc = da - db;
}
else
{
carry = true;
dc = (MAXDP1 + da) - db;
}
if (dc == 0)
{
if (zs == -1)
zs = i;
}
else
{
if (zs != -1)
{
for (int j = zs; j < i; j++)
c.data.Add(0);
zs = -1;
}
c.data.Add((uint)dc);
}
}
for (int i = nb; i < na; i++)
{
uint dc;
if (carry)
{
if (a.data[i] == 0)
dc = MAXD;
else
{
dc = a.data[i] - 1;
carry = false;
}
}
else
dc = a.data[i];
if (dc == 0)
{
if (zs == -1) zs = -1;
}
else
{
if (zs != -1)
{
for (int j = zs; j < i; j++)
c.data.Add(0);
zs = -1;
}
c.data.Add(dc);
}
}
c.sign = sign;
return c;
}
public VBI(uint val, int sign)
{
if (val == 0)
return;
this.sign = sign;
this.data.Add(val);
}
public static VBI operator +(VBI x, VBI y)
{
if (x.sign == 0)
return new VBI(y, 1);
if (y.sign == 0)
return new VBI(x, 1);
if (x.sign == y.sign)
return _add(x, y, x.sign);
return _sub(x, y, x.sign);
}
public static VBI operator -(VBI x, VBI y)
{
if (x.sign == 0)
return new VBI(y, -1);
if (y.sign == 0)
return new VBI(x, 1);
if (x.sign == y.sign)
return _sub(x, y, x.sign);
return _add(x, y, x.sign);
}
public static VBI parse(string s)
{
VBI r = new VBI();
if (string.IsNullOrEmpty(s))
return r;
int sign = 1;
if (s[0] == '-')
{
sign = -1;
s = s.Substring(1);
}
if (s.Length > 1000)
throw new Exception("String too long");
for (int i = 0; i < s.Length; i++)
{
int d = s[i] - '0';
if (d < 0 || d > 9)
throw new Exception("Invalid string");
if (r.sign != 0)
{
uint carry = 0;
for (int j = 0; j < r.data.Count; j++)
{
ulong p = (r.data[j]) * ((ulong)10) + ((ulong)carry);
r.data[j] = (uint)(p & MAXD);
carry = (uint)(p >> 32);
}
if (carry != 0)
r.data.Add(carry);
}
r = r + new VBI((uint)d, 1);
}
r.sign = r.data.Count == 0 ? 0 : sign;
return r;
}
public override string ToString()
{
if (sign == 0)
return "0";
StringBuilder ret = new StringBuilder();
VBI c = new VBI(this, 1);
while (c.data.Count > 0)
{
uint carry = 0;
int trailingZeroCount = 0;
bool trailingZeros = true;
for (int i = c.data.Count - 1; i >= 0; i--)
{
ulong d = (ulong)((ulong)carry << 32) + (ulong)c.data[i];
uint q = (uint)(d / 10);
c.data[i] = q;
if (q == 0)
{
if (trailingZeros)
trailingZeroCount++;
}
else
if (trailingZeros)
trailingZeros = false;
carry = (uint)(d % 10);
}
ret.Insert(0, carry);
for (int i = 0; i < trailingZeroCount; i++)
c.data.RemoveAt(c.data.Count - 1);
}
if (sign < 0)
ret.Insert(0, "-");
return ret.ToString();
}
}
class Program
{
static void Main(string[] args)
{
Console.WriteLine(VBI.parse("99999999999999999999") + VBI.parse("1"));
Console.WriteLine(VBI.parse("100000") - VBI.parse("1"));
}
}
Repsherrifjenkins, Applications Developer at ASAPInfosystemsPvtLtd
I am Sherri from Richmond USA. I am working as a Clinical laboratory technician worker in P. Samuels Men's ...
Repmoruytmeks, Airport service agent at Stratabiz
I am an airport service agent . I work in an airport , providing information and assistance to the flying public. In ...
O((m+n)*K) solution
- Tewelde December 06, 2015