資訊專欄INFORMATION COLUMN
摘要：題目要求輸入一個數(shù)組和一個值，刪除數(shù)組中等于該值得元素。但是在數(shù)組的容量非常大且數(shù)組中該數(shù)字出現(xiàn)頻率不高的情況下，使用兩個指針可以明顯減少程序遍歷數(shù)組的時間。
題目要求：輸入一個數(shù)組和一個值，刪除數(shù)組中等于該值得元素。不允許分配新的內(nèi)存空間（即不允許創(chuàng)建新的數(shù)組），允許數(shù)組中的元素的順序發(fā)生變化，只要該數(shù)組在返回長度前的值正確
例如：輸入nums = [3,2,2,3], val = 3，程序返回2，且nums數(shù)組的前兩個值均為2
使用一個指針
時間復(fù)雜度O(n), 空間復(fù)雜度O(1)
/**
* @author rale
* Given an array and a value, remove all instances of that value in place and return the new length.
* Do not allocate extra space for another array, you must do this in place with constant memory.
* The order of elements can be changed. It doesn"t matter what you leave beyond the new length.
* Example:
* Given input array nums = [3,2,2,3], val = 3
* Your function should return length = 2, with the first two elements of nums being 2.
*/
public class RemoveElement {
public int removeElement(int[] nums, int val) {
int index = 0;
for(int i = 0 ; i
使用兩個指針
時間復(fù)雜度O(n) 空間復(fù)雜度O(1)
/**
* @author rale
* Given an array and a value, remove all instances of that value in place and return the new length.
* Do not allocate extra space for another array, you must do this in place with constant memory.
* The order of elements can be changed. It doesn"t matter what you leave beyond the new length.
* Example:
* Given input array nums = [3,2,2,3], val = 3
* Your function should return length = 2, with the first two elements of nums being 2.
*/
public class RemoveElement {
public int removeElement(int[] nums, int val) {
if(nums==null || nums.length==0){
return 0;
}
int leftPointer = 0;
int rightPointer = nums.length-1;
while(leftPointer<=rightPointer){
if(nums[rightPointer]==val){
rightPointer--;
continue;
}
if(nums[leftPointer]==val){
nums[leftPointer] = nums[rightPointer];
rightPointer--;
}
leftPointer++;
}
return rightPointer+1;
}
}
leetcode的測試用例得出的性能分析發(fā)現(xiàn)，使用一個指針比使用兩個指針的速度更快。但是在數(shù)組的容量非常大且數(shù)組中該數(shù)字出現(xiàn)頻率不高的情況下，使用兩個指針可以明顯減少程序遍歷數(shù)組的時間。
leetcode上也給出了參考答案
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/66857.html
摘要：題目比較簡單，就是找出數(shù)組不重復(fù)的數(shù)字，返回不重復(fù)的數(shù)字個數(shù)。無需刪除重復(fù)數(shù)字，只需要保證數(shù)組的前位為不重復(fù)的個數(shù)字即可代碼如下 Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.Do not all...
給定一個排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個元素只出現(xiàn)一次，返回移除后數(shù)組的新長度。 不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。 Given a sorted array nums, remove the duplicates in-place such that each element appear only once and re...
給定一個排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個元素只出現(xiàn)一次，返回移除后數(shù)組的新長度。 不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。 Given a sorted array nums, remove the duplicates in-place such that each element appear only once and re...
摘要：給定一個排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個元素只出現(xiàn)一次，返回移除后數(shù)組的新長度。不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用額外空間的條件下完成。聲明兩個指針，為快指針，為慢指針如果遇到相同的數(shù)，那么就跳過，。 給定一個排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個元素只出現(xiàn)一次，返回移除后數(shù)組的新長度。不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組...
Problem Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical...
閱讀 1289·2021-11-11 16:55
閱讀 1551·2021-10-08 10:16
閱讀 1209·2021-09-26 10:20
閱讀 3591·2021-09-01 10:47
閱讀 2470·2019-08-30 15:52
閱讀 2697·2019-08-30 13:18
閱讀 3207·2019-08-30 13:15
閱讀 1145·2019-08-30 10:55
