-
-
Save JeffreyZhao/3999741 to your computer and use it in GitHub Desktop.
// As we all know, the generic List<T> class in .NET doesn't | |
// have a RemoveMultiple method. Could you implement it for me? | |
// Say the elements are kept in the _items field, which is an | |
// array of type T. Also, use _count to keep the current number | |
// of elements. | |
// PS: You can compare two items with "==" operator. | |
namespace System.Collections.Generic | |
{ | |
public class List<T> | |
{ | |
private T[] _items; | |
private int _count; | |
public void RemoveMultiple(IEnumerable<T> itemsToRemove) | |
{ | |
// Please implement the method here. | |
} | |
} | |
} |
egmkang
commented
Nov 2, 2012
public void RemoveMultiple(IEnumerable itemsToRemove)
{
bool findBegin = false;
int begin = 0;
int end = 0;
for(int current = 0; current < _count; current ++)
{
if(!itemsToRemove.Contains(_item[current]))
{
if(!findBegin)
{
findBegin = true;
begin = end = current;
}
else
{
if(current != end + 1)
{
T tmp = _item[current];
_item[current] = _item[end + 1];
_item[end + 1] = tmp;
}
}
}
}
}
mac上无环境,手写了一下
没有C 来个java版的.
public void RemoveMultiple(DemoList<T> removes) {
HashMap<T, Integer> map = new HashMap<T, Integer>();
for (T temp : removes._items) {
Integer count = map.get(temp);
if (count == null) {
map.put(temp, new Integer(-1));
} else {
count--;
map.put(temp, count);
}
}
List<T> myitem = new ArrayList<T>();
for (T temp : _items) {
Integer count = map.get(temp);
if (count == null) {
myitem.add(temp);
} else if(count <0) {
count++;
map.put(temp,count);
}else{
myitem.add(temp);
}
}
_items = (T[]) myitem.toArray();
_count = myitem.size();
}
public static void main(String[] args) {
System.out.println("112233");
DemoList<String> list = new DemoList<String>();
list._count =3;
list._items =new String[]{"1","1","1"};
DemoList<String> list2 = new DemoList<String>();
list2._count =2;
list2._items =new String[]{"1","1"};
list.RemoveMultiple(list2);
System.out.println(list._count);
System.out.println(list._items);
}
public void RemoveMultiple(IEnumerable<T> itemsToRemove) { bool findBegin = false; int begin = 0; int end = 0; for(int current = 0; current < _count; current++) { if(!itemsToRemove.Contains(_item[current])) { if(!findBegin) { findBegin = true; begin = end = current; } else { if(current != end + 1) { T tmp = _item[current]; _item[current] = _item[end + 1]; _item[end + 1] = tmp; } } } } }
@egmkang 版本不错
在winter老大的基础上改为计数,上面那个乱了。通过测试的
public void RemoveMultiple(IEnumerable itemsToRemove)
{
Dictionary index = new Dictionary();
foreach (var item in itemsToRemove)
{
if (index.ContainsKey(item))
index[item]++;
else
index.Add(item, 1);
}
var j = 0;
for (var i = 0; i < _count; i++)
{
if (!index.ContainsKey(_items[i]))
_items[j++] = _items[i];
else
{
if (index[_items[i]] > 1)
index[_items[i]]--;
else index.Remove(_items[i]);
}
}
_count = j;
}
赞@egmkang 的,最后给_count赋值就OK了。
public void RemoveMultiple(IEnumerable itemsToRemove)
{
foreach (T item in itemsToRemove)
{
for (int i = 0; i < _count; i++)
{
if (_items[i] == item)
{
_items[i] = null;
}
}
}
int p = 0;
int q = 0;
while (p != _count)
{
if (p != q)
{
if (_items[p] != null)
{
_items[q] = _items[p];
q++;
}
p++;
}
}
for (int i = q + 1; i < _count; i++)
{
_items[i] = null;
}
_count = q + 1;
}
晕,忘了preview了,重贴
public void RemoveMultiple(IEnumerable<T> itemsToRemove)
{
foreach (T item in itemsToRemove)
{
for (int i = 0; i < _count; i++)
{
if (_items[i] == item)
{
_items[i] = null;
}
}
}
int p = 0;
int q = 0;
while (p != _count)
{
if (p != q)
{
if (_items[p] != null)
{
_items[q] = _items[p];
q++;
}
p++;
}
}
for (int i = q + 1; i < _count; i++)
{
_items[i] = null;
}
_count = q + 1;
}
public class TestJava
{
@test
把可以自动生成的代码全删掉了 要不太长了。。
回复微博的时候立刻想到的是插入排序倒着来实现,想着简单,写下来还真是有点费劲,调试了一会儿。。
public void EestRemoveAll()
{
List list = new MyList();
list.add(2);
list.add(1);
list.add(2);
list.add(2);
list.add(2);
list.add(5);
list.add(2);
List subList = new ArrayList();
subList.add(2);
subList.add(2);
list.removeAll(subList);
printMyList(list);
}
public static void printMyList(List list)
{
for (int i = 0, length = list.size(); i < length; i++)
{
System.out.println(i + " " + list.get(i));
}
}
class MyList<E> implements List<E>
{
private Object[] elementArray;
private int size;
public MyList()
{
this(10);
}
public MyList(int size)
{
elementArray = new Object[size];
}
@Override
public int size()
{
return size;
}
@Override
public boolean add(E e)
{
checkAndIncreaseSize(size + 1);
elementArray[size++] = e;
return true;
}
private void checkAndIncreaseSize(int newLength)
{
if (size < elementArray.length)
{
//no need to increase array's size
return;
}
Arrays.copyOf(elementArray, elementArray.length * 2);
}
public boolean removeAll(Collection<?> c)
{
boolean result = false;
if (c == null || c.size() == 0)
{
return false;
}
for (int i = size - 1; i >= 0; i--)
{
if (c.contains(elementArray[i]))
{
//将要删除的数组向前挪
size--;
move(elementArray, i + 1, 1);
result = true;
}
}
return result;
}
/**
* 将 array从第几位开始,之后的每一项向前移几位
* @param array
* @param startIndex
* @param movedItemNumber
* @throws MyException
*/
private void move(Object[] array, int startIndex, int movedItemNumber) throws MyException
{
if (array == null || array.length == 0)
{
throw new MyException("");
}
if (startIndex >= array.length)
{
throw new MyException("");
}
//等于的时候相当于将最后一位置空
if (startIndex < array.length - 1)
{
if (startIndex < movedItemNumber)
{
throw new MyException("");
}
for (int i = startIndex, length = array.length; i < length; i++)
{
array[i - movedItemNumber] = array[i];
}
}
for (int i = 1, length = array.length; i <= movedItemNumber; i++)
{
array[length - i] = null;
}
}
@Override
public E get(int index)
{
return (E) elementArray[index];
}
}
class MyException extends RuntimeException
{
public MyException(String msg)
{
super(msg);
}
}
}
public void RemoveMultiple(IEnumerable<T> itemsToRemove)
{
bool findBegin = false;
int begin = -1;
int end = -1;
for(int current = 0; current < _count; current++)
{
if(!itemsToRemove.Contains(_item[current]))
{
if(!findBegin)
{
findBegin = true;
begin = end = current;
}
else
{
if(current != end + 1)
{
T tmp = _item[current];
_item[current] = _item[end + 1];
_item[end + 1] = tmp;
}
end++;
}
}
}
// new list from begin to end
for(int i = begin; i <=end; i++)
{
Console.Write(_item[i] + " ");
}
}
又看了下,发现少写 end ++ 逻辑,补充下
刚看了一下Dictionary的实现,貌似有一点2
如果要用Dictionary,也应该在初始化的时候把容量写一下啊。
尽量精简,一次遍历搞定
public void RemoveMultiple (IEnumerable<T> itemsToRemove)
{
lock (this) {
var hash = new HashSet<T>(itemsToRemove);
var count = _count;
for(int i = 0, k = 0; i<_count; i++){
if(hash.Contains(_items[i])){
count--;
}
else{
if( i != k ){
_items[k] = _items[i];
}
k++;
}
}
_count = count;
}
}
namespace System.Collections.Generic
{
public class List<T>
{
private T[] _items;
private int _count;
public void RemoveMultiple(IEnumerable<T> itemsToRemove)
{
var oldCount = _count;
var newItems = new T[oldCount];
var removeHashset = new HashSet<T>(itemsToRemove)
var insertPos = 0;
for (var i = 0; i < oldCount; i++)
{
var item = _items[i];
if(removeHashset.Contains(item))
continue;
newItems[insertPos++] = item;
}
_items = newItems;
_count = insertPos;
}
}
}
这个是面试题吗?
void Main()
{
var list = new List(new[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 });
var itemsToRemove = new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, };
list.Print();
list.RemoveMultiple(itemsToRemove);
list.Print();
}
// Define other methods and classes here
public class List
{
private T[] _items;
private int _count;
public List(IEnumerable<T> values)
{
_items = values.ToArray();
_count = _items.Length;
}
public void Print()
{
Console.WriteLine(string.Join(", ", _items.Take(_count).Select(x => x.ToString())));
}
public void RemoveMultiple(IEnumerable<T> itemsToRemove)
{
// Please implement the method here.
// == 无法通过编译, 这里用了 object.Equals
// 如果查找时间过长,并且可以排序,可以合并算法更快找出所有要删除的索引位置, 此处从略
var indeces = _items.Select((item, index) => new {item, index})
.Where(x => itemsToRemove.Any(y => Equals(y, x.item)))
.Select(x => x.index)
.OrderBy(x => x)
.ToList();
for(var i = 0; i < indeces.Count; i++)
{
var indexStart = indeces[i] - i;
var indexEnd = (i < indeces.Count - 1 ? indeces[i+1] : _count -1) -i;
for(var index = indexStart; index < indexEnd; index++)
{
_items[index] = _items[index+i+1];
}
}
_count = _count - indeces.Count;
}
}
void Main()
{
var list = new List<int>(new[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 });
var itemsToRemove = new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, };
list.Print();
list.RemoveMultiple(itemsToRemove);
list.Print();
}
// Define other methods and classes here
public class List<T>
{
private T[] _items;
private int _count;
public List(IEnumerable<T> values)
{
_items = values.ToArray();
_count = _items.Length;
}
public void Print()
{
Console.WriteLine(string.Join(", ", _items.Take(_count).Select(x => x.ToString())));
}
public void RemoveMultiple(IEnumerable<T> itemsToRemove)
{
// Please implement the method here.
// == 无法通过编译, 这里用了 object.Equals
// 如果查找时间过长,并且可以排序,可以合并算法更快找出所有要删除的索引位置, 此处从略
var indeces = _items.Select((item, index) => new {item, index})
.Where(x => itemsToRemove.Any(y => Equals(y, x.item)))
.Select(x => x.index)
.OrderBy(x => x)
.ToList();
for(var i = 0; i < indeces.Count; i++)
{
var indexStart = indeces[i] - i;
var indexEnd = (i < indeces.Count - 1 ? indeces[i+1] : _count -1) -i;
for(var index = indexStart; index < indexEnd; index++)
{
_items[index] = _items[index+i+1];
}
}
_count = _count - indeces.Count;
}
}
睡一半想到昨天写错了。。。
public void RemoveMultiple(IEnumerable<T> itemsToRemove)
{
foreach (T item in itemsToRemove)
{
for (int i = 0; i < _count; i++)
{
if (_items[i] == item)
{
_items[i] = null;
break;
}
}
}
int p = 0;
int q = 0;
while( p != _count )
{
if (!_items[p] == null)
{
if (p != q)
{
_items[q] = _items[p];
}
q++;
}
p++;
}
for (int i = q; i < _count; i++)
{
_items[i] = null;
}
_count = q;
}