renbin
BAN USERTime complexity is O(N), and does not need extra space. It is possible that long string could repeat short string for several times (e.g.: 1abc2abc -> abc), so i use a int[] to store all start indexes.
var shortarr = shortstr.ToArray();
var longarr = longstr.ToArray();
List<int> output = new List<int>();
int si = 0, li = 0;
while (li < longarr.Length)
{
while (li < longarr.Length && si < shortarr.Length && longarr[li] == shortarr[si])
{
li++;
si++;
}
if (si == shortarr.Length)
{
output.Add(li - si);
si = 0;
}
li++;
}
return output.ToArray();
This is a O(n2) complexity solution, but does not require extra space. The 2 input linked lists are inputted as an array 'list'.
for (int j = 0; j < list.Length; j++)
{
var node = list[j];
while (node != null)
{
var left = head;
while (left != curpos)
{
if (node.Value == left.Value)
{
break;
}
left = left.Next;
}
if (left == curpos && left.Value != node.Value)
{
curpos.Next = node;
curpos = curpos.Next;
}
node = node.Next;
}
}
curpos.Next = null;
return head;
Use below method to do in position replace, and time complex should be O(n).
int left = 0, right = array.Length - 1, i = 0;
while (i < right)
{
if (array[i] == 0)
{
Swap(array, i++, left++);
}
else if (array[i] == 1)
{
i++;
}
else if (array[i] == 2)
{
Swap(array, i++, right--);
}
}
We can use one integer O(n) in binary format (e.g.: 0b01101) to save which row or columns need to be set to zero during first full scan. Position 0->N used for columns, and N+1->M for rows, and 1 means to set to zero. And with the integer we can set the rows/columns to zero directly. The sample code is below:
int pos = 0; // Low bits for columns
for (int r = 0; r < rows; r++)
{
for (int c = 0; c < cols; c++)
{
if (matrix[r][c] == 0)
{
// Save bits
pos |= (1 << c);
pos |= (1 << (r + cols));
}
}
}
for (int c = 0; c < cols && pos > 0; c++)
{
if (0 < (pos & (1 << c)))
{
for (int r = 0; r < rows; r++)
{
matrix[r][c] = 0;
}
}
}
for (int r = 0; r < rows && pos > 0; r++)
{
if (0 < (pos & (1 << (cols + r))))
{
for (int c = 0; c < cols; c++)
{
matrix[r][c] = 0;
}
}
}
- renbin October 20, 2015