h*****g
发帖数: 312 | 1 2)/*
* Given an array and a value, remove all instances of that
* value in place and return the new length. The order of
* elements can be changed. It doesn't matter what you leave
* beyond the new length.
*/
size_t remove_elem(T* array, size_t len, T elem) {
}
这个题目他是想让用quick sort 类似的方法 从两头同时开始找，然后换，尽量减少交
换的次数
////////////////////////////////////////////////
这题从前到后sweep一遍就ＯＫ了吧？ quick sort得咋做？ |
e***l
发帖数: 710 | 2 前后2个指针，前面往后走，每次遇到given value,把后面指针的元素填过来，然后后
面的往前一步。直到相遇。 |
p*****2
发帖数: 21240 | 3 static int Remove(int[] arr, int v)
{
int start=0;
int end=arr.length-1;
while(start
{
while(arr[start]!=v)
start++;
while(arr[end]==v)
end--;
if(start
{
arr[start]=arr[end];
arr[end]=v;
start++;
end--;
}
}
return start;
} |
p*****2
发帖数: 21240 | 4 QuickSort
static void QuickSort(int[] arr, int start, int end)
{
int pivot=arr[(start+end)/2];
int l=start;
int r=end;
while(l
{
while(arr[l]
l++;
while(arr[r]>pivot)
r--;
if(l<=r)
{
int tmp=arr[l];
arr[l]=arr[r];
arr[r]=tmp;
l++;
r--;
}
}
if(start
QuickSort(arr,start,l-1);
if(end>l)
QuickSort(arr,l,end);
} |
H***e
发帖数: 476 | 5 这跟quicksort有啥关系？
从前往后一遍就行了吧，两个指针，一个指向有用的数据最后一个，一个current,如果
current不是target,就把此数据考向前面的指针
【在 h*****g 的大作中提到】
: 2)/*
: * Given an array and a value, remove all instances of that
: * value in place and return the new length. The order of
: * elements can be changed. It doesn't matter what you leave
: * beyond the new length.
: */
: size_t remove_elem(T* array, size_t len, T elem) {
: }
: 这个题目他是想让用quick sort 类似的方法 从两头同时开始找，然后换，尽量减少交
: 换的次数
|
H***e
发帖数: 476 | 6 你现在每题都当场练啊
写这个程序加调要多久？
【在 p*****2 的大作中提到】
: QuickSort
: static void QuickSort(int[] arr, int start, int end)
: {
: int pivot=arr[(start+end)/2];
: int l=start;
: int r=end;
: while(l: {
: while(arr[l]: l++;
|
p*****2
发帖数: 21240 | 7
没算时间。大概20分钟吧。不过我以前练过这个程序。前两天突然发现忘记了，所以又
看了看算法，今天正好有机会练习一下。就按照前两天的记忆写的。
【在 H***e 的大作中提到】
: 你现在每题都当场练啊
: 写这个程序加调要多久？
|
a*****n
发帖数: 158 | 8 这个应该和 DUTCH Flag那个问题比较象吧。。。。 |
n******d
发帖数: 386 | 9 赞
【在 h*****g 的大作中提到】
: 2)/*
: * Given an array and a value, remove all instances of that
: * value in place and return the new length. The order of
: * elements can be changed. It doesn't matter what you leave
: * beyond the new length.
: */
: size_t remove_elem(T* array, size_t len, T elem) {
: }
: 这个题目他是想让用quick sort 类似的方法 从两头同时开始找，然后换，尽量减少交
: 换的次数
|
s****e
发帖数: 638 | 10 有bug. 这个arr可能不含 v.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
【在 p*****2 的大作中提到】
:
: 没算时间。大概20分钟吧。不过我以前练过这个程序。前两天突然发现忘记了，所以又
: 看了看算法，今天正好有机会练习一下。就按照前两天的记忆写的。
|
|
|
p*****2
发帖数: 21240 | 11
是。
【在 s****e 的大作中提到】
: 有bug. 这个arr可能不含 v.
:
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|
h********w
发帖数: 221 | |
P***P
发帖数: 1387 | 13 qsort最好上点median of 3， 还要注意array有重复的情况
【在 p*****2 的大作中提到】
: QuickSort
: static void QuickSort(int[] arr, int start, int end)
: {
: int pivot=arr[(start+end)/2];
: int l=start;
: int r=end;
: while(l: {
: while(arr[l]: l++;
|
z******t
发帖数: 59 | 14 在博客中分析了这个问题：
http://codercareer.blogspot.com/2012/02/no-32-remove-numbers-in
博客中的思路和peking2的思路是一样的。博客中的代码删除了两行不必要的代码（If
中的++和--不是必须的，因为在while循环里这两个操作都要做）。
【在 p*****2 的大作中提到】
:
: 是。
|
j**w
发帖数: 382 | 15 void swap(T *array, size_t i, size_t j)
{
if (i != j)
{
T temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
size_t remove_elem(T* array, size_t len, T elem)
{
size_t i = 0;
size_t j = len-1;
while (( i < len ) && ( i < j ))
{
if (array[i].equals(elem))
{
swap(array, i, j);
j--;
}
else
{
i++;
}
}
return j+1;
} |
j********x
发帖数: 2330 | 16 remove erase idiom
把符合条件的先放到末尾，完成之后抹掉
或者前后两个指针，一个维护应该保留的元素，一个维护当前插入的位置
覆盖不需要保留的元素即可
【在 h*****g 的大作中提到】
: 2)/*
: * Given an array and a value, remove all instances of that
: * value in place and return the new length. The order of
: * elements can be changed. It doesn't matter what you leave
: * beyond the new length.
: */
: size_t remove_elem(T* array, size_t len, T elem) {
: }
: 这个题目他是想让用quick sort 类似的方法 从两头同时开始找，然后换，尽量减少交
: 换的次数
|
H*****1
发帖数: 4815 | 17 不用sort啊
就是一个指针在前，一个指针在后
前面指针遇到elem，就跟后一个指针换，后一个指针前移一位
前面指针如果不是elem，就后移一位，直到前面指针和后面指针相等
length就是后面指针-array
【在 h*****g 的大作中提到】
: 2)/*
: * Given an array and a value, remove all instances of that
: * value in place and return the new length. The order of
: * elements can be changed. It doesn't matter what you leave
: * beyond the new length.
: */
: size_t remove_elem(T* array, size_t len, T elem) {
: }
: 这个题目他是想让用quick sort 类似的方法 从两头同时开始找，然后换，尽量减少交
: 换的次数
|
e****e
发帖数: 418 | 18 I think "If 中的++和--不是必须的" is a little bit inefficient.
Because it's 100% sure that after if clause, arr[start] != v and arr[end]==v
is true. We can just increase both start and end variable by 1 inside if
clause. Why wait till enter the next round of the outer while loop and let
two inner while loops do the increasing by 1 work?
If
【在 z******t 的大作中提到】
: 在博客中分析了这个问题：
: http://codercareer.blogspot.com/2012/02/no-32-remove-numbers-in
: 博客中的思路和peking2的思路是一样的。博客中的代码删除了两行不必要的代码（If
: 中的++和--不是必须的，因为在while循环里这两个操作都要做）。
|
e****e
发帖数: 418 | 19 replace start
【在 s****e 的大作中提到】
: 有bug. 这个arr可能不含 v.
:
: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|
i**********e
发帖数: 1145 | 20 这里首先有个判定条件错了，应该是 ( i <= j ) 而不是 ( i < j )。
反例：【4,5】，remove 5.
还有一点就是做了很多不必要的交换，例如：
【1,2,2,2,2】，remove 2.这里用了不必要的三次交换。 |
i**********e
发帖数: 1145 | 21 试试：
数组【1】，remove 2.
If
【在 z******t 的大作中提到】
: 在博客中分析了这个问题：
: http://codercareer.blogspot.com/2012/02/no-32-remove-numbers-in
: 博客中的思路和peking2的思路是一样的。博客中的代码删除了两行不必要的代码（If
: 中的++和--不是必须的，因为在while循环里这两个操作都要做）。
|
H***e
发帖数: 476 | 22 有bug啊
ps, while inside while 极容易出错啊。
我现在都是把里面的 while 用continue delegate给外面的
【在 p*****2 的大作中提到】
:
: 是。
|
