Java教程

经典数据结构题目-数组

本文主要是介绍经典数据结构题目-数组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

704. 二分查找

  • 解决思路

    • 基于数组有序的特性,取其中一个值进行比较,即可淘汰该值左边或右边的元素,缩小搜索的区间
    • 使用两指针标记需要遍历的区间,取中间值进行比较,淘汰左边或右边元素,不断移动缩小遍历的区间,即可查到
  • 代码

    public int search(int[] nums, int target) {
            int l = 0;
            int r = nums.length - 1;
            while(l <= r){  // 注意点一
                int mid = l + (r-l)/2;
                if(nums[mid] > target){
                    r = mid - 1; // 注意点二
                }else if(nums[mid] < target){
                    l = mid + 1;
                }else{
                    return mid;
                }
            }
            return -1; 
        }
    
  • 注意点

    • 核心注意点:避免漏检元素
    • 注意点一:while条件中选择 l <= r 还是 l < r ,取决于 r 的取值;当 r = num.length时,l 不能 <= r,可能会溢出
    • 注意点二:当选择 l < r 的判断时,while中每次搜索的区间为 [l,r) 。当num[mid] > target时,r = mid,不能mid-1。因为r所指向的元素在进入第二次循环时,是不会再与target比较,会导致漏检
    • 时间复杂度 O(logN) 。总共需要遍历 log2N次,忽略常数2。
  • 扩展

    • 当元素可重复时,如何定位到与target相等的最小索引

    • public static int search(int[] nums, int target) {
              int l = 0;
              int r = nums.length - 1;
              while(l <= r){
                  int mid = l + (r-l)/2;
                  if(nums[mid] >= target){
                      // 等于target的时候 右指针继续移动,继续寻找最左边的一个
                      // 如果已达最左的一个,再循环左指针会移动,最终会大于r,取到最左的
                      r = mid - 1;
                  }else if(nums[mid] < target){
                      l = mid + 1;
                  }
              }
              // 会存在找不到与target相等的情况
              if(nums.length == l || nums[l] != target){
                  return -1;
              }
              return l;
          }
      

80. 删除有序数组中的重复项 II

  • 解决思路

    • 使用快慢指针遍历,快指针用于判断是否与上一个元素重复,慢指针用于记录下最终有效的数字
    • 快指针判断为不重复,慢指针记下来,同时向前移动一位
  • 代码

        public int removeDuplicates(int[] nums) {
            // 只允许元素出现一次的情况
            int k = 1;
            int fast = k;
            int slow = k; // 注意点一
            while(fast < nums.length){
                if(nums[fast] != nums[fast-k]){ // 注意点二
                    nums[slow] = nums[fast];
                    slow++;
                }
                fast ++;
            }
            return slow;
        }
    
  • 注意点

    • 核心注意点:理清快慢指针分别的作用
    • 注意点一:快慢指针的起始位置,k <= nums.length时,可以初始化快慢指针在k的位置开始遍历
    • 注意点二:判断元素是否超过k个重复,因为数组有序,如果当前元素等于前k个位置的元素,说明超过了
  • 同类型题目

    • https://leetcode.cn/problems/remove-element/description/
    • https://leetcode.cn/problems/move-zeroes/description/

977. 有序数组的平方

  • 解决思路

    • 非递减顺序。即递增但可以重复
    • 使用双向指针,比较两指针指向元素的绝对值,绝对值大的计算平方添加进结果数组
  • 代码

     public int[] sortedSquares(int[] nums) {
            int[] res = new int[nums.length];
            int l = 0;
            int r = nums.length-1;
            int index = nums.length - 1;
            while(l <= r){
                if(Math.abs(nums[l]) > Math.abs(nums[r])){
                    res[index] = (int)Math.pow(nums[l],2);
                    l++;
                }else{
                    res[index] = (int)Math.pow(nums[r],2);
                    r--;
                }
                index --;
            }
            return res;
        }
    
  • 注意点

    • 这里空间复杂度为O(1),不是O(n),因为空间复杂度是计算非答案占用的空间
  • 扩展

    • 想再节省空间的话,可以比较两个数的平方后,进行交换,右指针一直往前移即可

    • public int[] SortedSquares(int[] nums) {
          int left = 0;
          int right = nums.length-1;
          int leftR = 0, rightR = 0;
          while(right >= 0){
            leftR = nums[left]*nums[left];
            rightR = nums[right]*nums[right];
            // 左指针的平方比较大,交换到数组的后面来
            if(leftR >= rightR){
              nums[left] = nums[right];
              nums[right] = leftR;
            }else{
              nums[right] = rightR;
            }
            right--;
          }
          return nums;
      }
      

这篇关于经典数据结构题目-数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!