LeetCode: 2576. 求出最多标记的下标 排序+双指针,时间复杂度O(n*logn)
2576. 求出最多标记的下标
today 2576 求出最多标记的下标
题目描述
给你一个下标从 0
开始的整数数组 nums 。
一开始,所有下标都没有被标记。你可以执行以下操作任意次:
选择两个互不相同且未标记 的下标i
和 j
,满足 2 * nums[i] <= nums[j]
,标记下标 i
和 j
。
请你执行上述操作任意次,返回 nums
中最多可以标记的下标数目。
示例1:
输入:nums = [3,5,2,4]
输出:2
解释:第一次操作中,选择 i = 2 和 j = 1 ,操作可以执行的原因是 2 * nums[2] <= nums[1] ,标记下标 2 和 1 。
没有其他更多可执行的操作,所以答案为 2 。
示例2:
输入:nums = [9,2,5,4]
输出:4
解释:第一次操作中,选择 i = 3 和 j = 0 ,操作可以执行的原因是 2 * nums[3] <= nums[0] ,标记下标 3 和 0 。
第二次操作中,选择 i = 1 和 j = 2 ,操作可以执行的原因是 2 * nums[1] <= nums[2] ,标记下标 1 和 2 。
没有其他更多可执行的操作,所以答案为 4 。
示例3:
输入:nums = [7,6,8]
输出:0
解释:没有任何可以执行的操作,所以答案为 0 。
提示:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
题目解析
题目要求我们,找出数组中最多可以标记的下标数目。
我们需要成对找出满足 2 * nums[i] <= nums[j]
的数字。
也就是说,每一个较小的数,需要找到一个大的数来配对。我们首先可以对数组进行排序,然后使用双指针法来找出满足条件的数字对。设置左指针为left
用于指向较小的数,右指针为right
用于指向较大的数。我们很容易知道,较小的数,应该全部在nums
数组的左半部分,较大的数应该全部在nums
的右半部分。因此有0<=left<len(nums)/2-1
, len(nums)/2<=right<len(nums)
。
初始化left=0
用于标记数组中最小的数。初始化right=len(nums)/2
用于标记数组中较大的数中最小的数。
-
如果
nums[left] * 2 <= nums[right]
,则我们可以标记left
和right
,并将left
右移一位,right
左移一位。 -
如果
nums[left] * 2 > nums[right]
,则我们需要将right
右移一位。
直到left
或right
超出边界条件,我们就找到了所有满足条件的数字对。
复杂度分析:
- 时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
- 空间复杂度为 O ( 1 ) O(1) O(1)
代码实现
Python实现:
class Solution(object):
def maxNumOfMarkedIndices(self, nums):
n = len(nums)
if n == 1:
return 0
nums.sort()
ans = 0
i, right = 0, n // 2
# 双指针遍历
while i < n // 2 and right < n:
if nums[i] * 2 <= nums[right]:
ans += 2
i += 1
right += 1
else:
right += 1
return ans
Go实现:
func maxNumOfMarkedIndices(nums []int) int {
n:=len(nums)
if(n==1){
return 0
}
ans:=0
sort.Ints(nums)
left, right := 0, n/2
for left<n/2 && right<n {
if nums[left]*2<=nums[right]{
left++
right++
ans+=2
}else{
right++
}
}
return ans
}
C++实现:
class Solution {
public:
int maxNumOfMarkedIndices(vector<int>& nums) {
int n=nums.size();
sort(nums.begin(),nums.end());
int left=0,right=n/2;
int ans=0;
while(left<n/2&&right<n){
if(nums[left]*2<=nums[right]){
left++;
right++;
ans+=2;
}else{
right++;
}
}
return ans;
}
};