一、852.⼭脉数组的峰顶索引

题目链接:852.⼭脉数组的峰顶索引
题目描述:

题目解析:

  • 给我们一个数组,元素是先递增在递减的,让我们返回最大元素下标。

1.1 二分查找

解题思路:

  • 我们这个数组本来就是一个被天然分成两段,递增区间和递减区间,的数据,天然使用二分查找的题。
  • 当mid的元素小于后一个元素的时候,mid在递增区间,所以left = mid + 1。
  • 当mid的元素大于后一个元素的时候,mid在递减区间,所以right = mid。

解题代码:

//时间复杂度:O(logN)
//空间复杂度:O(1)
class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0;
        int right = arr.length-1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(arr[mid] < arr[mid+1]) left = mid + 1;
            else right = mid;
        }
        return left;
    }
}

1.2 暴力枚举

解题思路:

  • 直接使用for循环遍历数组,该下标元素大于前面和后面元素,返回下标。
  • 因为这个数组一定是一个山脉数组,所以不用管数组头和尾。

解题代码:

//时间复杂度:O(n)
//空间复杂度:O(1)
class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        for(int i = 1; i < arr.length - 1; i++) {
            if(arr[i] > arr[i-1] && arr[i] > arr[i+1]) return i;
        }
        return 0;
    }
}

二、162.寻找峰值

题目链接:162.寻找峰值
题目描述;

题目解析:

  • 给我们的数组是,递增递减反复进行,让我们找到其中一个峰值的下标。
  • 数组可能是这几个情况:1 . /\/\/\ ,2. / ,3. \

2.1 二分查找

解题思路:

  • 其实我们可以将数组分为,有要求峰值和没有要求峰值两段,因为给了峰值不等于下一个元素。
  • 所以当mid小于下一个元素的时候,mid就是在没有要求峰值那段,left = mid+1。
  • 当mid大于下一个元素的时候,mid就是在有峰值那段,right = mid

解题代码:

//时间复杂度:O(logN)
//空间复杂度:O(1)
class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < nums[mid + 1]) left = mid + 1;
            else right = mid; 
        }
        return left;
    }
}

2.2 暴力枚举

解题思路:

  • 直接转变为求数组最大值下标,遍历数组即可。

解题代码:

//时间复杂度:O(n)
//空间复杂度:O(1)
class Solution {
    public int findPeakElement(int[] nums) {
        int ret = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] > nums[ret])  ret = i;
        }
        return ret;
    }
}

三、153.寻找旋转排序数组中的最⼩值

题目链接:153.寻找旋转排序数组中的最⼩值
题目描述:

题目解析:

  • 数组旋转一次就代表将数组尾元素放在数组头。
  • 给我们一个原来升序的数组,旋转多次后,找到数组中最小元素下标。
  • 数组中元素各不相同。
  • 数组会是下面这种状态或者一个完全递增的状态

3.1 二分查找

解题思路:

  • 我们这个数组本来就是已经是被分成两段了的。
  • 我们可以使用nums[ 0 ]或者nums[ nums.length - 1 ]来当分界线。
  • 使用nums[ nums.length - 1 ]为界限:
    • mid元素大于等于界限时,在数组段1,所以left = mid + 1。
    • mid元素小于界限的时候,在数组段2,所以right = mid。
  • 使用nums[ 0 ]为界限:
    • mid元素大于等于界限时,在数组段1,所以left = mid + 1。
    • mid元素小于界限的时候,在数组段2,所以right = mid。
    • 考虑数组完全递增时,nums[0]才是最小值。

解题代码:

//时间复杂度:O(logN)
//空间复杂度:O(1)
//使用nums[ nums.length - 1 ]为界限:
class Solution {
    public int findMin(int[] nums) {
        int left  = 0;
        int right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < nums[nums.length-1]) right = mid;
            else left = mid + 1;
        }
        return nums[left];
    }
}
//使用nums[ 0 ]为界限:
class Solution {
    public int findMin(int[] nums) {
        int left  = 0;
        int right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] >= nums[0]) left = mid + 1;
            else right = mid;
        }
        if(nums[0] < nums[left]) left = 0;
        return nums[left];
    }
}

3.2 暴力枚举

解题思路;

  • 直接循环遍历数组找最小值即可。

解题代码:

//时间复杂度:O(n)
//空间复杂度:O(1)
class Solution {
    public int findMin(int[] nums) {
        int ret = nums[0];
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] < ret) ret = nums[i];
        }
        return ret;
    }
}

四、LCR 173.点名

题目链接:LCR 173.点名
题目描述:

题目解析:

  • 给你一个长度为n数组,这个数组中有0到n中的数,按升序排列,找出数组在0到n中不含有的数。

4.1 二分查找

解题思路:

  • 这个数组分为这样两段,一段是下标与元素值相同的,一段是下标是元素值减1。
  • 所以当mid元素等于mid的时候,落在第一段,left = mid + 1;
  • 当mid元素不等于mid的时候,落在第二段,right = mid。

解题代码:

//时间复杂度:O(logN)
//空间复杂度:O(1)
class Solution {
    public int takeAttendance(int[] records) {
        int left = 0;
        int right = records.length;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(records[mid] == mid) left = mid + 1;
            else right = mid;
        }
        return left;
    }
}

4.2 哈希表

解题思路:

  • 借助一个数组来标记0到n中出现过的元素。

解题代码:

//时间复杂度:O(n)
//空间复杂度:O(n)
class Solution {
    public int takeAttendance(int[] records) {
        int[] hash = new int[records.length + 1];
        for(int i = 0; i < records.length; i++) {
            hash[records[i]]++;
        }
        for(int i = 0; i < hash.length; i++) {
            if(hash[i] == 0) return i;
        }
        return 0;
    }
}

4.3 暴力枚举

解题思路:

  • 直接遍历数组,当出现第一个下标和元素不相等的直接返回元素减一即可。
  • 遍历完数组还是没找到,证明是0到n中n不在数组中。

解题代码:

//时间复杂度:O(n)
//空间复杂度:O(1)
class Solution {
    public int takeAttendance(int[] records) {
        for(int i = 0; i < records.length; i++) {
            if(records[i] != i) return records[i]-1;
        }
        return records.length;
    }
}

4.4 位运算

解题思路:

  • 直接使用一个变量来将0到n的数全部异或。
  • 在于数组元素进行异或。

解题代码:

//时间复杂度:O(n)
//空间复杂度:O(1)
class Solution {
    public int takeAttendance(int[] records) {
        for(int i = 0; i < records.length; i++) {
            if(records[i] != i) return records[i]-1;
        }
        return records.length;
    }
}

4.5 数学(求和)

解题思路:

  • 直接先将0到n的和求出来。
  • 在减去数组中的元素即可。

解题代码:

//时间复杂度:O(n)
//空间复杂度:O(1)
class Solution {
    public int takeAttendance(int[] records) {
        int n = records.length;
        int ret = (n*(n+1))/2;
        for(int i = 0; i < records.length; i++) {
            ret = ret - records[i];
        }
        return ret;
    }
}
Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐