検索挿入位置
3394 ワード
26章ソートされた配列から重複を削除する
容易
整数配列
nums
非減少順序でソートされ、重複を取り除くin-place 各ユニークな要素が1回だけ表示されます.要素の相対的な順序は同じに保たれるべきです.いくつかの言語で配列の長さを変更することは不可能ですので、代わりに結果を配列の最初の部分に配置する必要があります
nums
. もっと正式に、もしあればk
重複を削除した後の要素、次にk
元素nums
は、最終的な結果を保持する必要があります.それはあなたが最初の角k
要素.リターン
k
最後の結果を最初に配置した後k
スロットnums
.別の配列に余分なスペースを割り当てることはできません.入力配列を変更することでこれをしなければなりませんin-place を用いる.
カスタムジャッジ
次のコードを使用してソリューションをテストします
int[] nums = [...]; // Input array int[] expectedNums = [...]; // The expected answer with correct length int k = removeDuplicates(nums); // Calls your implementation assert k == expectedNums.length; for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i]; }
If all assertions pass, then your solution will be accepted.
Example 1:
Input: nums = [1,1,2] Output: 2, nums = [1,2,_] Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).
Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5, nums = [0,1,2,3,4,_,_,_,_,_] Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively. It does not matter what you leave beyond the returned k (hence they are underscores).
Constraints:
1 <= nums.length <= 3 * 104
-100 <= nums[i] <= 100
-
nums
is sorted in non-decreasing order.
Python Solution Using an Iterative approach
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
for i in range(len(nums)):
if nums[i] >= target:
return i
break
elif nums[i] > target and target < nums[i + 1]:
return i+1
break
elif target > nums[-1]:
return len(nums)
elif target < nums[0]:
return 0
break
return i
時間複雑性:O(n)補助空間: O ( 1 )
より良い代替--バイナリ検索を使用するPythonソリューション。
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
n = len(nums)
start = 0
end = n - 1
while start <= end:
mid = (start + end) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
start = mid + 1
else:
end = mid - 1
return end + 1
時間複雑性:O(log n)補助空間: O ( 1 )
Reference
この問題について(検索挿入位置), 我々は、より多くの情報をここで見つけました https://dev.to/isaacttonyloi/search-insert-position-4akcテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol