leetcode刷题笔记

day 1(2024/3/19)

题目: 26.删除有序数组中的重复项

难度: 简单

分析

看到这道题的第一反应就是创建一个新的数组,然后遍历原数组,将值不断的放进新的数组中.

但是仔细看题目,发现需要原地删除重复出现的元素,因此上述的方法就不可行了.

那么应该怎么办呢? 根据题目的要求,发现我们只需要保证前k个元素是唯一且递增的就行,后续的数组如何并不重要. 因此,我们可以遍历整个数组,然后将不同的k个值放在前k个元素中就行.

比方说:

0	0	1	1	1	2	2	3	3	4

上面这个数组,我们要做的就是将数组变成这样子.

0	1	2	3	4	x	x	x	x	x

至于后面的x是什么,我们并不在意.

因此,我们可以遍历整个数组,然后通过一个index来记录我们所遇到的不同的值,每次遇到不同的值就将这个值放到对应的index中,并且将index加一.

代码

C语言

int removeDuplicates(int* nums, int numsSize) {    
    if(numsSize ==0){
        return 0;
    //特殊情况判断,当数组长度为0,直接返回0
    }
    
    int max=  nums[0]; //用来记录我们所遇到的最大的值,遍历的时候进行比较,当遇到的值比max大的时候,说明是第一次遇到这个值
    int index = 1; 
    for(int i = 0;i<numsSize;i++){
        if(nums[i]>max){
            max = nums[i];
            nums[index] = max;
            index++;
        }
    }
    return index;
}

python

class Solution(object):
    def removeDuplicates(self, nums):
        ans = 1
        max = nums[0]
        for i in range(len(nums)):
            if nums[i]>max:
                max = nums[i]
                nums[ans] = max
                ans+=1

        return ans

day 2(2024/3/20)

题目：35.搜索插入位置

难度：简单

分析

最开始看到这题目，觉得十分简单，一个遍历，然后比较，就解决了。

提交完代码看到解释，发现并没有这么做。后来重新看题目，发现把时间复杂度为O(log n)看错了。

那么看到O(log n)，第一反应就是二分法。

那么怎么进行二分法呢？由于可能会出现target不在数组中的情况，因此需要在二分法的时候额外考虑这种情况。

因此，我们可以将所有的情况分成两种：

1. target在数组中
2. target不在数组中：
   1. target小于所有数组中的数字，插入在数组第一个位置
   2. target大于所有数组中的数字，插入在数组最后的位置
   3. target插入在数组中间

当target在数组中的时候，我们正常的二分法就可以了。

由于数组是排序好的，因此我们可以直接和数组的第一个数字和最后一个数组进行判断

如果小于第一个或者大于最后一个，直接就可以输入结果。只有当target要插入在数组中间的时候才需要使用二分法进行判断

而如果使用二分法，由于我们知道target不在数组中，那么最后二分法的情况就是最后一次判断后没办法继续再分了，而我们就需要在最后一次判断后得到target需要插入的位置。

x	x	nums[left]	nums[right]	x	x	x

最后就会出现类似上面的情况，而我们所需要插入的位置，就是这两个数之间，也就是left+1

代码：

C语言

原本的二分法思路:

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0; 
        int right = nums.length-1;
        int ans = -1; 
        if(target<nums[0]){  //当target小于数组中最小的数
            return 0;
        }
        else if(target>nums[nums.length-1]){ //当target大于数组中最大的数
            return nums.length;
        }
        else{ 
            while(right - left>1){ // 当right>left + 1的时候,说明right和left之间还有数可以进行判断,只有当两个数的差小于等于1的时候,才说明这是最后一次二分.
                int index = (left+right)/2;
                if(nums[index]==target){
                    return index;
                }
                else if(nums[index] >target){
                    right = index;
                }
                else{
                    left = index;
                }
            }
            //当最后一次二分结束后,我们需要对target所插入的位置进行判断
            // 1.两者都不等,说明target不在数组中,需要插入两个数之间,也就是left+1
            if(nums[left] != target && nums[right] !=target){
                ans = left+1;
            }
            // 当target和其中一个数相等的时候,就直接将ans赋值
            if(nums[left] ==target){
                ans = left;
            }
            if(nums[right]==target){
                ans = right;
            }
        }
        return ans;
    }
}

简易的二分法:

int searchInsert(int* nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1, ans = numsSize;
    while (left <= right) {
        int mid = ((right - left) >> 1) + left;
        if (target <= nums[mid]) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}

python

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        ans = len(nums)
        right = len(nums)-1
        while(left <= right):
            index = (left + right) //2
            if(nums[index]>=target):
                ans = index
                right = index-1
            else:
                left = index+1
        return ans