[代码随想录]----数组(自用)

[代码随想录]----数组(自用)

文章目录

• 1、二分查找
• • leetcode704二分查找
  • • 题解
• 2、移除元素
• • leetcode27移除元素
  • • 题解
• 3、有序数组的平方
• • leetcode977有序数组的平方
  • • 题解
• 4、长度最小的子数组
• • leetcode209长度最小的子数组
  • • 题解

1、二分查找 leetcode704二分查找

https://leetcode-cn.com/problems/binary-search/

题解

两种写法只有在//标注处有区别（共2处）

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

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

2、移除元素 leetcode27移除元素

https://leetcode-cn.com/problems/remove-element/submissions/

题解

使用双指针的思想，类似的题还有[leetcode初级算法]的第一题，删除重复元素。题目地址https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2gy9m/，在笔者写的另一篇博客里也写了，可参考。（https://blog.csdn.net/z_2_0_/article/details/121373996）

int removeElement(int* nums, int numsSize, int val){
    int i = 0;
    int j = 0;
    for(; i < numsSize; i++)
    {
        if(nums[i] != val)
        {
            nums[j] = nums[i];
            j++;
        }
    }
    return j;
}

3、有序数组的平方 leetcode977有序数组的平方

https://leetcode-cn.com/problems/squares-of-a-sorted-array/

题解

本题值得注意的就是根据数组元素的特点来判断它应该位于那个位置：偶数次方（或者绝对值）会改变数据的大小关系。但是我们肯定能确定的是，最值所在位置一定是在首/末：因为它已经是单调不减的了。

int* sortedSquares(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    int* ans;
    ans = (int*)malloc(sizeof(int) * numsSize);
    int i = 0;
    int j = numsSize - 1;
    int k = numsSize - 1;
    while( i < numsSize)//原数组各元素平方
    {
        nums[i] = nums[i] * nums[i];
        i++;
    }
    i = 0;
    for( ;i <= j;)//进行排序
    {
        if(nums[i] >= nums[j])
        {
            ans[k] = nums[i];
            i++;
        }
        else
        {
            ans[k] = nums[j];
            j--;
        }
        k--;
    }
    return ans;
}

4、长度最小的子数组 leetcode209长度最小的子数组

https://leetcode-cn.com/problems/minimum-size-subarray-sum/

题解