平武建站

【代码训练营】day1|704.二分查找&27.移除元素-创新互联

目录
  • 数组基础
    • 数组理论知识
  • 二分查找 Leetcode704
    • 题目连接：[二分查找 Leetcode704 - 简单](https://leetcode.cn/problems/binary-search/)
    • 思路
    • java代码
    • 总结
  • 移除元素 Leetcode27
    • 题目链接：[移除元素 Leetcode27 - 简单](https://leetcode.cn/problems/remove-element/)
    • 思路
    • java代码
    • 总结

在清河门等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供网站设计、成都做网站 网站设计制作按需求定制制作,公司网站建设,企业网站建设,成都品牌网站建设,成都全网营销,成都外贸网站建设,清河门网站建设费用合理。数组基础 数组理论知识

注意：

  • 数组的下标都从0开始
  • 数组的内存地址是连续的

在这里插入图片描述

由于数组地址是连续的，所以在删除或插入元素的时候，都要移动后面的元素

  对于二维数组的话，C++是地址是连续的，java不连续。 java的地址如下图：

java内存地址

二分查找 Leetcode704 题目连接：二分查找 Leetcode704 - 简单 思路

本题主要有两种解法：一是左闭右闭[ , ]，一种是左闭右开[ , )，在大部分的题型中都采用左闭右开的方法。

java代码

1、左闭右闭

public int search(int[] nums, int target) {   int left = 0;
       int right = nums.length - 1;
       // 左闭右闭的情况可以取到中间的值
       //如[01234],当left=2 right=2 target=2，若letf  // int middle = (left + right) / 2; 可能会溢出
          int middle = left + ((right - left)>>1);
           if (nums[middle]< target){// [,target]目标值在右边 
               left = middle + 1; // 调整左区间[middle+1,]，左为闭区间 要 +1
           }else if(nums[middle] >target){// [target,]目标值在左边 
               right = middle - 1;	// 调整右区间[,middle-1]，右为闭区间 要 -1
           }else {   return middle; // 找到则返回下标
           }
       }
       return -1;
    }

2、左闭右开

public int search(int[] nums, int target) {int left = 0;
        int right = nums.length; // 这里不-1
        // 因为右边取不到，所以不用取等
        //如[01234],当target=2 left=2 right=3时就返回了，所以不用取等
        while (left< right){int middle = left + ((right - left) >>1);
            if (nums[middle]< target){// [,target)在目标值右边
                left = middle + 1;  // 左为闭区间要 + 1
            }else if(nums[middle] >target){// [target,)在目标值左边
                right = middle; // 右边取不到的，直接取等
            }else {return middle;
            }
        }
        return -1;
    }
总结

1、遇到问题：在写左闭右开的时提交一直不对，是由于没考虑到right = nums.length此时右区间不用减一，因为右区间取不到。
2、注意： 取中间值最好用位运算middle = left + ((right - left) >>1)，虽然直接写middle = (left + right) / 2也能通过，但是就怕其他情况出现溢出。还有一个注意点就是middle的位置和left ?= right

移除元素 Leetcode27 题目链接：移除元素 Leetcode27 - 简单 思路

此题不能有额外的数组空间，也就是进行原地修改，修改后直接返回数组长度就实行了。所以把需要修改元素位置找到，后面的再依次填充就好了
- - 双指针解法
快指针：指向数组下标，若不是目标值就更新，是目标值就跳过。
慢指针：指向更新数组的下标

java代码

1、暴力解法

public int removeElement(int[] nums, int val) {   int count = nums.length;
       // i   if (nums[i] == val){   for (int j = i+1; j< count; j++) {   nums[j-1] = nums[j];
               }
//                System.out.println("看一下nums" +  Arrays.toString(nums));
               i--;
               count--;
           }
       }
       return count;
   }

2、双指针（推荐）

public int removeElement(int[] nums, int val) {// 慢指针，用于存储新的数组元素，每次储存一位就后移一位
        int slow = 0;
        // 快指针，用于复制原数组里面不包含val的数
        for (int fast = 0; fast< nums.length; fast++) {if (nums[fast] != val){nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
总结

1、遇到的问题： 在写暴力的时候一直输出错误，错在我一开始写的循环结束条件为i< nums.length，但是这样就没有考虑到每次后移最后就是目标值，这样就会进入死循环。
2、熟练使用双指针可解决大部分数组的题，若不太会就画出图或是打输出语句。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


分享名称：【代码训练营】day1|704.二分查找&27.移除元素-创新互联
文章URL：http://pwwzsj.com/article/jdhjp.html

其他资讯