迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. 1 public static int RemoveDuplicatesfromSortedArray(int[] A) 2 { 3 int prev = A[0]; 4 int numtoremove = 0; 5 int ret = A.Length; 6 7 for (int i = 1; i < ret; i++) 8 { 9 if (prev == A[i]) 10 { 11 numtoremove++; 12 } 13 else 14 { 15 if(numtoremove > 0) 16 RemoveDuplicatesfromSortedArrayShiftLeft(A, ret, i, numtoremove); 17 ret -= numtoremove; 18 i -= numtoremove; 19 numtoremove = 0; 20 prev = A[i]; 21 } 22 } 23 24 if (numtoremove > 0) 25 { 26 ret -= numtoremove; 27 } 28 29 return ret; 30 } 31 32 public static void RemoveDuplicatesfromSortedArrayShiftLeft(int[] A, int alength, int index, int n) 33 { 34 for (int i = index; i < alength; i++) 35 { 36 A[i - n] = A[i]; 37 } 38 } 代码分析: 不难,用numtoremove存着几个重复的,然后remove掉(拷贝后面的上来)就可以了。 注意容易出错的是,ret(数组长度)要记得改,i 要记得改, prev 要记得改, numtoremove 要记得清零。 还有记得处理corner case, 重复的在最后一个数。 |
请发表评论