i**********n
发帖数: 196 | 1 write a function which takes as input a sorted array A of integers and a
positive integer m, and updates A so that if x appears m times in A, it
appears exactly min(2,m) times in A. The update to A should be in one pass,
and no additional storage may be allocated.
求简洁算法。 |
j*****8
发帖数: 3635 | 2 lc原题的小变形，加个condition check就行
public int removeDuplicates(int[] A, int m) {
if(A == null || A.length == 0) return 0;
int index = 1, count = 0;
for(int i = 1; i < A.length; i++) {
if(A[i] == A[index-1]) {
if(m >= 2 && count < 1) {//keep it
A[index] = A[i];
index++;
count++;
}
} else {
if(count > 0) count = 0;
A[index] = A[i];
index++;
}
}
return index;
} |
y*******8
发帖数: 112 | |
l*****a
发帖数: 14598 | 4 可以不要count吧，直接跟i-2比较即可
【在 j*****8 的大作中提到】
: lc原题的小变形，加个condition check就行
: public int removeDuplicates(int[] A, int m) {
: if(A == null || A.length == 0) return 0;
: int index = 1, count = 0;
: for(int i = 1; i < A.length; i++) {
: if(A[i] == A[index-1]) {
: if(m >= 2 && count < 1) {//keep it
: A[index] = A[i];
: index++;
: count++;
|
j*****8
发帖数: 3635 | 5 有道理，多谢大牛指点
【在 l*****a 的大作中提到】
: 可以不要count吧，直接跟i-2比较即可
|
y*******8
发帖数: 112 | 6 不可以比较i 和 i-1 i-2，会覆盖掉之前的数值，导致后面的比较不准啊。
http://codesays.com/2014/solution-to-remove-duplicates-from-sor
【在 l*****a 的大作中提到】
: 可以不要count吧，直接跟i-2比较即可
|
l*****a
发帖数: 14598 | 7 其实不是i了
弄个read/write 2 index
看A[read] and A[write-2]
does that make sense?
【在 y*******8 的大作中提到】
: 不可以比较i 和 i-1 i-2，会覆盖掉之前的数值，导致后面的比较不准啊。
: http://codesays.com/2014/solution-to-remove-duplicates-from-sor
|
y*******8
发帖数: 112 | 8 Make sense. 我最开始的答案就是用的相似的方法。
但是jingi08 的解法个人觉得更好，因为更加通用。min(2,m)可以这么做，min(3,m)或
者min(4,m)都可以。只要加一个参数就可以了。然后比较if count <= M:决定写不写。
当然两种代码都可以过。http://codesays.com/2014/solution-to-remove-duplicates-from-sorted-array-ii-by-leetcode/
我还在苦苦找第一份工作，经验肯定不如前辈，可能考虑不周，请多指教！
【在 l*****a 的大作中提到】
: 其实不是i了
: 弄个read/write 2 index
: 看A[read] and A[write-2]
: does that make sense?
|
l*****a
发帖数: 14598 | 9 那把A[write-2]换成A[write-k]是不是就可以了呢？
关于算法，有工作经验的不见得比在校生强吧
【在 y*******8 的大作中提到】
: Make sense. 我最开始的答案就是用的相似的方法。
: 但是jingi08 的解法个人觉得更好，因为更加通用。min(2,m)可以这么做，min(3,m)或
: 者min(4,m)都可以。只要加一个参数就可以了。然后比较if count <= M:决定写不写。
: 当然两种代码都可以过。http://codesays.com/2014/solution-to-remove-duplicates-from-sorted-array-ii-by-leetcode/
: 我还在苦苦找第一份工作，经验肯定不如前辈，可能考虑不周，请多指教！
|
y*******8
发帖数: 112 | 10 那复杂度就上去了，是O(N*K)了。用个变量存count复杂度始终会是O(N)。
K是容许重复的最大次数。
【在 l*****a 的大作中提到】
: 那把A[write-2]换成A[write-k]是不是就可以了呢？
: 关于算法，有工作经验的不见得比在校生强吧
|
|
|
i**********n
发帖数: 196 | 11 非常elegant的解法！受教了。
【在 j*****8 的大作中提到】
: lc原题的小变形，加个condition check就行
: public int removeDuplicates(int[] A, int m) {
: if(A == null || A.length == 0) return 0;
: int index = 1, count = 0;
: for(int i = 1; i < A.length; i++) {
: if(A[i] == A[index-1]) {
: if(m >= 2 && count < 1) {//keep it
: A[index] = A[i];
: index++;
: count++;
|
a*******3
发帖数: 13 | 12 updates A so that if x appears m times in A, it appears exactly min(2,m)
times in A.
这题意思不应该是如果一个数在数组里面正好出现了m次，才把这个数的出现次数调整
为min(2.,m)么？如果这个数出现次数不等于m次不应该全部保留下来么？
还是说我理解有问题。。？ |
i**********n
发帖数: 196 | 13 取2和m中的较小者。
【在 a*******3 的大作中提到】
: updates A so that if x appears m times in A, it appears exactly min(2,m)
: times in A.
: 这题意思不应该是如果一个数在数组里面正好出现了m次，才把这个数的出现次数调整
: 为min(2.,m)么？如果这个数出现次数不等于m次不应该全部保留下来么？
: 还是说我理解有问题。。？
|
l*****a
发帖数: 14598 | 14 why O(N*K)呢？
每个需要处理K次？没有啊
【在 y*******8 的大作中提到】
: 那复杂度就上去了，是O(N*K)了。用个变量存count复杂度始终会是O(N)。
: K是容许重复的最大次数。
|
B********t
发帖数: 147 | 15 class Solution {
public:
int removeDuplicates(int A[], int n) {
if (n <= 2) return n;
int c = 0, l = 0, r = 0;
while (r < n) {
while (r < n && A[l] == A[r]) r++;
l = r - l > 2 ? r - 2 : l;
while (l != r) A[c++] = A[l++];
}
return c;
}
}; |
t***t
发帖数: 6066 | 16 新学位能拿新的CPT么？我觉得你直接找工作为好。刷题进flg，visa对他们应该没问题
。 |
h*******e
发帖数: 1377 | 17 这是程序论坛的bug? 我怎么在讨论rmv duplicate II 里看到你的回复了。
【在 t***t 的大作中提到】
: 新学位能拿新的CPT么？我觉得你直接找工作为好。刷题进flg，visa对他们应该没问题
: 。
|
i**********n
发帖数: 196 | 18 write a function which takes as input a sorted array A of integers and a
positive integer m, and updates A so that if x appears m times in A, it
appears exactly min(2,m) times in A. The update to A should be in one pass,
and no additional storage may be allocated.
求简洁算法。 |
j*****8
发帖数: 3635 | 19 lc原题的小变形，加个condition check就行
public int removeDuplicates(int[] A, int m) {
if(A == null || A.length == 0) return 0;
int index = 1, count = 0;
for(int i = 1; i < A.length; i++) {
if(A[i] == A[index-1]) {
if(m >= 2 && count < 1) {//keep it
A[index] = A[i];
index++;
count++;
}
} else {
if(count > 0) count = 0;
A[index] = A[i];
index++;
}
}
return index;
} |
y*******8
发帖数: 112 | |
|
|
l*****a
发帖数: 14598 | 21 可以不要count吧，直接跟i-2比较即可
【在 j*****8 的大作中提到】
: lc原题的小变形，加个condition check就行
: public int removeDuplicates(int[] A, int m) {
: if(A == null || A.length == 0) return 0;
: int index = 1, count = 0;
: for(int i = 1; i < A.length; i++) {
: if(A[i] == A[index-1]) {
: if(m >= 2 && count < 1) {//keep it
: A[index] = A[i];
: index++;
: count++;
|
j*****8
发帖数: 3635 | 22 有道理，多谢大牛指点
【在 l*****a 的大作中提到】
: 可以不要count吧，直接跟i-2比较即可
|
y*******8
发帖数: 112 | 23 不可以比较i 和 i-1 i-2，会覆盖掉之前的数值，导致后面的比较不准啊。
http://codesays.com/2014/solution-to-remove-duplicates-from-sor
【在 l*****a 的大作中提到】
: 可以不要count吧，直接跟i-2比较即可
|
l*****a
发帖数: 14598 | 24 其实不是i了
弄个read/write 2 index
看A[read] and A[write-2]
does that make sense?
【在 y*******8 的大作中提到】
: 不可以比较i 和 i-1 i-2，会覆盖掉之前的数值，导致后面的比较不准啊。
: http://codesays.com/2014/solution-to-remove-duplicates-from-sor
|
y*******8
发帖数: 112 | 25 Make sense. 我最开始的答案就是用的相似的方法。
但是jingi08 的解法个人觉得更好，因为更加通用。min(2,m)可以这么做，min(3,m)或
者min(4,m)都可以。只要加一个参数就可以了。然后比较if count <= M:决定写不写。
当然两种代码都可以过。http://codesays.com/2014/solution-to-remove-duplicates-from-sorted-array-ii-by-leetcode/
我还在苦苦找第一份工作，经验肯定不如前辈，可能考虑不周，请多指教！
【在 l*****a 的大作中提到】
: 其实不是i了
: 弄个read/write 2 index
: 看A[read] and A[write-2]
: does that make sense?
|
l*****a
发帖数: 14598 | 26 那把A[write-2]换成A[write-k]是不是就可以了呢？
关于算法，有工作经验的不见得比在校生强吧
【在 y*******8 的大作中提到】
: Make sense. 我最开始的答案就是用的相似的方法。
: 但是jingi08 的解法个人觉得更好，因为更加通用。min(2,m)可以这么做，min(3,m)或
: 者min(4,m)都可以。只要加一个参数就可以了。然后比较if count <= M:决定写不写。
: 当然两种代码都可以过。http://codesays.com/2014/solution-to-remove-duplicates-from-sorted-array-ii-by-leetcode/
: 我还在苦苦找第一份工作，经验肯定不如前辈，可能考虑不周，请多指教！
|
y*******8
发帖数: 112 | 27 那复杂度就上去了，是O(N*K)了。用个变量存count复杂度始终会是O(N)。
K是容许重复的最大次数。
【在 l*****a 的大作中提到】
: 那把A[write-2]换成A[write-k]是不是就可以了呢？
: 关于算法，有工作经验的不见得比在校生强吧
|
i**********n
发帖数: 196 | 28 非常elegant的解法！受教了。
【在 j*****8 的大作中提到】
: lc原题的小变形，加个condition check就行
: public int removeDuplicates(int[] A, int m) {
: if(A == null || A.length == 0) return 0;
: int index = 1, count = 0;
: for(int i = 1; i < A.length; i++) {
: if(A[i] == A[index-1]) {
: if(m >= 2 && count < 1) {//keep it
: A[index] = A[i];
: index++;
: count++;
|
a*******3
发帖数: 13 | 29 updates A so that if x appears m times in A, it appears exactly min(2,m)
times in A.
这题意思不应该是如果一个数在数组里面正好出现了m次，才把这个数的出现次数调整
为min(2.,m)么？如果这个数出现次数不等于m次不应该全部保留下来么？
还是说我理解有问题。。？ |
i**********n
发帖数: 196 | 30 取2和m中的较小者。
【在 a*******3 的大作中提到】
: updates A so that if x appears m times in A, it appears exactly min(2,m)
: times in A.
: 这题意思不应该是如果一个数在数组里面正好出现了m次，才把这个数的出现次数调整
: 为min(2.,m)么？如果这个数出现次数不等于m次不应该全部保留下来么？
: 还是说我理解有问题。。？
|
|
|
l*****a
发帖数: 14598 | 31 why O(N*K)呢？
每个需要处理K次？没有啊
【在 y*******8 的大作中提到】
: 那复杂度就上去了，是O(N*K)了。用个变量存count复杂度始终会是O(N)。
: K是容许重复的最大次数。
|
t***t
发帖数: 6066 | 32 新学位能拿新的CPT么？我觉得你直接找工作为好。刷题进flg，visa对他们应该没问题
。 |
h*******e
发帖数: 1377 | 33 这是程序论坛的bug? 我怎么在讨论rmv duplicate II 里看到你的回复了。
【在 t***t 的大作中提到】
: 新学位能拿新的CPT么？我觉得你直接找工作为好。刷题进flg，visa对他们应该没问题
: 。
|
f**********t
发帖数: 1001 | 34 // write a function which takes as input a sorted array A of integers and a
positive integer m, and updates A so that if x appears m times in A, it
appears exactly min(2,m) times in A. The update to A should be in one pass,
and no additional storage may be allocated.
void deduplicate(vector &A, unsigned m) {
if (A.size() < 3 || m < 3) {
return;
}
unsigned count = 1;
int pre = A[0];
unsigned left = 0;
unsigned copyIdx = 0;
for (unsigned right = 1; right < A.size(); ++right) {
if (A[right] == pre) {
++count;
} else {
unsigned bar = right;
if (count == m) {
bar = left + 2;
}
while (left < bar) {
A[copyIdx++] = A[left++];
}
left = right;
pre = A[right];
count = 1;
}
}
unsigned bar = A.size();
if (count == m) {
bar = left + 2;
}
while (left < bar) {
A[copyIdx++] = A[left++];
}
A.erase(A.begin() + copyIdx, A.end());
} |
f**********t
发帖数: 1001 | 35 Will, if the dup is m - 1, or m + 1 ....., it need to be all copied, based
on what 楼主 said.
【在 j*****8 的大作中提到】
: lc原题的小变形，加个condition check就行
: public int removeDuplicates(int[] A, int m) {
: if(A == null || A.length == 0) return 0;
: int index = 1, count = 0;
: for(int i = 1; i < A.length; i++) {
: if(A[i] == A[index-1]) {
: if(m >= 2 && count < 1) {//keep it
: A[index] = A[i];
: index++;
: count++;
|
