代码随想录day1---LeetCode704二分查找&27移除元素

标签：right target nums int 随想录 mid 27 移除 left

LeetCode 704二分查找[https://leetcode.cn/problems/binary-search/]

题目：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
分析：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功
我的代码（java&python）：没有使用while循环来判断left与right情况，是使用递归来进行后续处理，比较笨拙，当时真的没想到，直接写了哈哈

点击查看代码

public class Solution {
  
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        return compare(nums,target,left,right);
     }
    public int compare(int[] nums, int target, int left, int right){
        int mid = (left + right)/2;
        if(nums[mid]==target){
            return mid;
        }else if(nums[mid]>target){
            right=mid-1;
            if(left>right){
                return -1;
            }
            return compare(nums,target,left,right);
        }else {
            left=mid+1;
            if (left>right){
                return -1;
            }
            return compare(nums,target,left,right);
        }
    }

}

点击查看代码

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right = len(nums)-1
        return self.compare(nums, target, left, right)
    def compare(self, nums, target, left, right):
        mid = (left + right)/2
        if nums[mid] == target:
            return mid
        elif nums[mid] > target:
            right = mid-1
            if(left>right):
                return -1
            return self.compare(nums, target, left, right)
        else:
            left = mid+1
            if(left>right):
                return -1
            return self.compare(nums, target, left, right)

* 查看视频及文章后，对于前闭后闭区间写法（java&python）：

点击查看代码

public class Solution {
    
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left<=right){//此处要有=，因为左闭右闭情况需要考虑到最右值
            int mid=(left+right)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]>target){
                right=mid-1;
            }else {
                left=mid+1;
            }
        }
        return -1;
    }
}

点击查看代码

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right = len(nums)-1
        while left <= right:
            mid = (left + right)/2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        return -1

前闭后开区间写法（java&python）:

点击查看代码

public class Solution704_s {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;//前闭后开区间，right指向元素取不到，此处right应取nums的length
        while (left < right) {//此处不应有=，因为right指向元素取不到
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid;//此处right取mid,因为right指向元素取不到，所以让其取mid
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

点击查看代码

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right = len(nums)
        while left < right:
            mid = (left + right)/2
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid
            else:
                left = mid + 1
        return -1

LeetCode27移除元素[https://leetcode.cn/problems/remove-element/]

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:

为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
分析：由于题目说可以不需要考虑超出长度后的元素以及可以改变顺序，我使用计数+交换，即用count来计算与val相同的元素个数，然后把每个和val相同的元素都替换到数组的最后，用一个right来控制未遍历且未交换过的最右边元素。
我的代码（java&python）：

点击查看代码

public class Solution {
    public int removeElement(int[] nums, int val) {

        int count=0;
        int right=nums.length-1;
        for (int i=0;i<right+1;i++){
            if(right<0){
                return nums.length-count;
            }
            if(nums[i]==val){
                count++;
                nums[i]=nums[right];
                nums[right]=val;
                right--;
                i--;
            }
        }
        return nums.length-count;
    }
    
}

点击查看代码

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        count = 0
        right = len(nums) - 1
        i = 0
        while i < right+1:
            if right < 0:
                return len(nums) - count
            if nums[i] == val:
                count = count + 1
                nums[i] = nums[right]
                nums[right] = val
                right = right - 1
                i = i - 1
            i = i + 1
        return len(nums) - count

查看视频及文章后，练习暴力解法（java&python）：

点击查看代码

public class Solution27_bl {

    //暴力破解
    public int removeElement(int[] nums, int val) {
        int length = nums.length;
        for(int i=0;i<length;i++){
            if(nums[i]==val){

                for(int j=i;j<length-1;j++){
                    nums[j]=nums[j+1];
                }
                length--;
                i--;
            }
        }
        return length;

    }
}

点击查看代码

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        length = len(nums)
        i = 0
        while i < length:
            if nums[i] == val:
                for j in range(i, length-1):
                    nums[j] = nums[j+1]
                length = length - 1
                i = i - 1
            i = i + 1
        return length

查看视频及文章后，练习双指针法，即快慢指针，快指针遍历数组，慢指针在原数组上操作新数组元素，最后慢指针指向下标即为新数组长度大小（java&python）：

点击查看代码

public class Solution27_szz {
    //双指针法
    public int removeElement(int[] nums, int val) {
        int slow=0;
        for(int fast=0;fast<nums.length;fast++){
            if(nums[fast]!=val){
                nums[slow]=nums[fast];
                slow++;
            }
        }
        return slow;
    }
}

点击查看代码

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        slow = 0
        for fast in range(0, len(nums)):
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow = slow + 1
        return slow

总结：
第一天的题目比较简单，实现起来没有什么问题，看了卡哥的视频和文章，更能清晰了解算法思想及加深印象，希望自己能够保持学习节奏多多练习~

标签：right,target,nums,int,随想录,mid,27,移除,left
From： https://www.cnblogs.com/LiHua-Koi/p/16898017.html

代码随想录day1---LeetCode704二分查找&27移除元素

相关文章

赞助商

阅读排行