資訊專欄INFORMATION COLUMN
摘要：題目要求輸入一個(gè)數(shù)組和一個(gè)值，刪除數(shù)組中等于該值得元素。但是在數(shù)組的容量非常大且數(shù)組中該數(shù)字出現(xiàn)頻率不高的情況下，使用兩個(gè)指針可以明顯減少程序遍歷數(shù)組的時(shí)間。
題目要求：輸入一個(gè)數(shù)組和一個(gè)值，刪除數(shù)組中等于該值得元素。不允許分配新的內(nèi)存空間（即不允許創(chuàng)建新的數(shù)組），允許數(shù)組中的元素的順序發(fā)生變化，只要該數(shù)組在返回長(zhǎng)度前的值正確
例如：輸入nums = [3,2,2,3], val = 3，程序返回2，且nums數(shù)組的前兩個(gè)值均為2
使用一個(gè)指針
時(shí)間復(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
使用兩個(gè)指針
時(shí)間復(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的測(cè)試用例得出的性能分析發(fā)現(xiàn)，使用一個(gè)指針比使用兩個(gè)指針的速度更快。但是在數(shù)組的容量非常大且數(shù)組中該數(shù)字出現(xiàn)頻率不高的情況下，使用兩個(gè)指針可以明顯減少程序遍歷數(shù)組的時(shí)間。
leetcode上也給出了參考答案
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/66857.html
摘要：題目比較簡(jiǎn)單，就是找出數(shù)組不重復(fù)的數(shù)字，返回不重復(fù)的數(shù)字個(gè)數(shù)。無(wú)需刪除重復(fù)數(shù)字，只需要保證數(shù)組的前位為不重復(fù)的個(gè)數(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...
給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次，返回移除后數(shù)組的新長(zhǎng)度。 不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。 Given a sorted array nums, remove the duplicates in-place such that each element appear only once and re...
給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次，返回移除后數(shù)組的新長(zhǎng)度。 不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。 Given a sorted array nums, remove the duplicates in-place such that each element appear only once and re...
摘要：給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次，返回移除后數(shù)組的新長(zhǎng)度。不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用額外空間的條件下完成。聲明兩個(gè)指針，為快指針，為慢指針如果遇到相同的數(shù)，那么就跳過(guò)，。 給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次，返回移除后數(shù)組的新長(zhǎng)度。不要使用額外的數(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...
閱讀 1344·2021-11-11 16:55
閱讀 1630·2021-10-08 10:16
閱讀 1272·2021-09-26 10:20
閱讀 3673·2021-09-01 10:47
閱讀 2522·2019-08-30 15:52
閱讀 2745·2019-08-30 13:18
閱讀 3265·2019-08-30 13:15
閱讀 1206·2019-08-30 10:55
