27:要素の除去
8939 ワード
問題の説明
配列numsと値valを指定すると、valに等しいすべての数値の要素をその場で除去し、除去後の配列の新しい長さを返す必要があります.余分な配列空間を使用しないでください.入力配列をその場で変更し、O(1)余分な空間を使用する条件で完了する必要があります.要素の順序は変更できます.配列の中で新しい長さの後ろを超える要素を考慮する必要はありません.
例
構想
この問題は二重ポインタでやります.1番目のポインタは真の長さtrueIndexを指し、2番目のポインタは現在の要素curを指し、curが指す要素がvalに等しい場合、trueIndexは更新されません.最後にtrueIndexを返します.(方法一)二重ポインタのもう一つの遊び方は,この配列にbadCaseがないと直接仮定することである.すなわちmaxIndexは最終的な配列長である.遍歴中にvalが見つかった場合、配列位置-1と同時に現在の配列の最後の要素をvalの位置にしなければなりません.過去の要素がvalかどうか分からないという弊害があります.私たちは過去にcurIndexを自増させないで、次のサイクルで判断を続けることができます.また、curとmaxIndexが同じ要素を指し、valに等しい場合はどうしますか?このときmaxIndexは必ず自滅します.覚えてる?我々が仮定したmaxIndexは最終的な配列長であり,直接返すとよい.(方法2)推薦方法1.分かりやすい方法2.方法2は効率的に方法より少し高いかもしれませんが、どこにも行けません.方法1.valではない要素がいくつあるか、n+valではない要素文コードを歩きます.方法2.n文コードを歩きます.ここで私たちの二重ポインタは同時に中間に移動しているからです.
図解
方法1
メソッド1 Java版
方法1 Python版
方法2
Java版
配列numsと値valを指定すると、valに等しいすべての数値の要素をその場で除去し、除去後の配列の新しい長さを返す必要があります.余分な配列空間を使用しないでください.入力配列をその場で変更し、O(1)余分な空間を使用する条件で完了する必要があります.要素の順序は変更できます.配列の中で新しい長さの後ろを超える要素を考慮する必要はありません.
例
nums = [3,2,2,3], val = 3,
2, nums 2。
。
nums = [0,1,2,2,3,0,4,2], val = 2,
5, nums 0, 1, 3, 0, 4。
。
。
構想
この問題は二重ポインタでやります.1番目のポインタは真の長さtrueIndexを指し、2番目のポインタは現在の要素curを指し、curが指す要素がvalに等しい場合、trueIndexは更新されません.最後にtrueIndexを返します.(方法一)二重ポインタのもう一つの遊び方は,この配列にbadCaseがないと直接仮定することである.すなわちmaxIndexは最終的な配列長である.遍歴中にvalが見つかった場合、配列位置-1と同時に現在の配列の最後の要素をvalの位置にしなければなりません.過去の要素がvalかどうか分からないという弊害があります.私たちは過去にcurIndexを自増させないで、次のサイクルで判断を続けることができます.また、curとmaxIndexが同じ要素を指し、valに等しい場合はどうしますか?このときmaxIndexは必ず自滅します.覚えてる?我々が仮定したmaxIndexは最終的な配列長であり,直接返すとよい.(方法2)推薦方法1.分かりやすい方法2.方法2は効率的に方法より少し高いかもしれませんが、どこにも行けません.方法1.valではない要素がいくつあるか、n+valではない要素文コードを歩きます.方法2.n文コードを歩きます.ここで私たちの二重ポインタは同時に中間に移動しているからです.
図解
方法1
メソッド1 Java版
public int removeElement(int[] nums, int val) {
int trueIndex = 0;
for(int curIndex = 0; curIndex < nums.length; curIndex++){
if(nums[curIndex]!=val){
nums[trueIndex++] = nums[curIndex];
}
}
return trueIndex;
}
方法1 Python版
class Solution:
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
cont = 0
for i, v in enumerate(nums):
if v == val: #
continue
else: # , ' '
nums[cont] = v
cont += 1
return cont
方法2
Java版
public int removeElement1(int[] nums, int val){
int curIndex = 0, maxIndex = nums.length-1;
while(curIndex<=maxIndex){
if(nums[curIndex] == val){
nums[curIndex] = nums[maxIndex--];
}else{
curIndex++;
}
}
return maxIndex+1;
}