《剑指offer》专题—算法训练 day01

亦凉 2022-09-11 03:10 52阅读 0赞

### 文章目录 ###

*  《剑指offer》专题—算法训练 day01
 *  一、二维数组的查找
 *   *  思路一
     *  思路二
 *  二、旋转数字的最小数字
 *   *  思路一
     *  思路二
 *  三、奇偶互换
 *   *  相对位置变化
     *  相对位置不变
 *  四、数组中出现次数超过一半的数字
 *   *  思路一
     *  思路二
     *  思路三

# 《剑指offer》专题—算法训练 day01 #

从今天起，博主开始了 《 剑指offer 》 系列 算法专题的学习，希望大家 跟随着博主一起，开始这段美妙的算法之旅…

# 一、二维数组的查找 #

题目链接：

[https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?][https_www.nowcoder.com_practice_abc3fe2ce8e146608e868a70efebf62e]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16]

## 思路一 ##

> 暴力算法

分析：直接遍历一遍数组，即可判断目标target是否存在。

public class Solution {
        
    
        public boolean Find(int target, int [][] array) {
        
        
        // 先for 循环遍历一下 数组的每一行
        
            for(int i = 0;i<array.length;i++){
        
        
            // 再 for 循环遍历一下数组这一行的每一列
        
                for(int j = 0;j<array[0].length;j++){
        
        
                // 判断每一个元素是否是我们需要的target
        
                     if(array[i][j] == target){
        
                         return true;
                     }
                }
                
            }
                        return false;
        }
    }

## 思路二 ##

查找的过程 本质是 排除的 过程

> 我们用暴力算法 一次只能排除一个，效率很低

我们可以利用这个题中矩阵的性质

> 每一行从左到右依次递增

> 每一列从上到下依次递增

我们会发现右上角的值 是所在行中最大的，同时也是所在列中 最小的.

那么我们每次查找 target 值时，都与这个矩阵 右上角的值进行比较

> 如果 小于 右上角，那么可以排除这一列

> 如果 大于 右上角 ， 那么可以排除这一行

好了，我们根据这个思路可以写出代码：

public class Solution {
        
        public boolean Find(int target, int [][] array) {
        
          int i = 0;
          int j = array[0].length-1;
            
            while(i<=array.length-1 && j>=0){
        
                
    //             array[i][j]一定是当前行最大，当前列最小的数
    //              target < array[i][j] 排除当前列
                
                if(target<array[i][j]){
        
                    j--;
                    
    //                 target> array[i][j] 排除当前行
                
                }else if(target >array[i][j]){
        
                    i++;
                    
    //                 target == array[i][j] 此时找到 对应元素，返回true
                
                }else{
        
                    return true;
                }
            }
            
    //         如果循环跳出，那么说明没有找到对应的元素，此时返回 false
            
            return false;
        }
    }

# 二、旋转数字的最小数字 #

题目链接：

[https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?][https_www.nowcoder.com_practice_9f3231a991af4f55b95579b44b7a01ba]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 1]

## 思路一 ##

> 本质其实是一个求最小值问题

理论上，遍历一次即可

import java.util.ArrayList;
    public class Solution {
        
        public int minNumberInRotateArray(int [] array) {
        
            
            if(array == null || array.length == 0){
        
                return 0;
            }
            
            int min = array[0];
            
            for(int i = 1;i<array.length;i++){
        
                if(min>array[i]){
        
                    min = array[i];
                }
            }
            
            return min;
        }
    }

## 思路二 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 2]

> 按照要求，要么是一个非递减排序的数组（最小值在最开始），要么是一个旋转(最小值在中间某个地方)

> 而且，旋转之后有个特征，就是在遍历的时候，原始数组是非递减的，旋转之后，就有可能出现递减，引起递减的数字，就 是最小值

采用二分查找的方式，进行定位

> 定义首尾下标，因为是非递减数组旋转，所以旋转最后可以看做成两部分，前半部分整体非递减，后半部分整体非递减，前 半部分整体大于后半部分。

> 所以，我们假设如下定义，left指向最左侧，right指向最右侧，mid为二分之后的中间位置。

> 则，a\[mid\] >= a\[left\],说明mid位置在原数组前半部分，进一步说明，目标最小值，在mid的右侧，让left=mid

> a\[mid\] < a\[left\], 说明mid位置在原数组后半部分，进一步说明，目标最小值，在mid的左侧，让right=mid

> 这个过程，会让\[left, right\]区间缩小

> 这个过程中，left永远在原数组前半部分，right永远在原数组的后半部分，而范围会一直缩小

两种情况：

> 当left和right相邻时，right指向的位置，就是最小元素的位置

> 但是，因为题目说的是非递减，也就意味着数据允许重复，因为有重复发，就可能会有arr\[left\] == arr\[mid\] == arr\[right\]的情况，我们就无法判定数据在mid左侧还是右侧。（注意，只要有两者不相等，我们就能判定应该如何缩小范围）

相关代码：

//  二分查找
    
    import java.util.ArrayList;
    public class Solution {
        
        public int minNumberInRotateArray(int [] array) {
        
          
          // 判断数组是否为空 以及 数组内容是否为空
            
            if(array == null || array.length == 0){
        
                return 0;
            }
            
            int left = 0;
            int right = array.length-1;
            int mid = 0;
            
            while(array[left]>=array[right]){
        
              // 这里的循环条件是 因为是旋转数组所以左区间最小的值 大于等于右区间最大的值                
    
              
              // 这种 情况是 当区间缩小到只有两个元素是，右边那个是最小的数字
              if(right-left ==1){
        
                    mid = right;
                    break;
                }
                
                mid = (left +right)/2;
              
              // 这种情况是 当 左 中 右 三值都相等时，我们无法判断 mid下标元素在左区间还是右区间
              // 我们只能从头遍历，查找数组中的最小值
              
                if(array[left] == array[mid] && array[mid] == array[right]){
                 
                    int result = array[left];
                    
                    for(int i = left+1;i<right;i++){
        
                      
          // 我们不需要从 left 开始遍历 ，还有最后 不用 <= right，因为 arr[left] = arr[right] ,我们不用再去判断         
                      if(array[i]<result){
        
                            result = array[i];
                        }
                      
                    }
                    
                    return result;
                    
                }
                
     //下面的这个判断就是 mid元素 大于 left元素，那么mid 在左区间，而我们要查找的最小数字在右区间,所以left=mid,缩小区间
              
                if(array[mid]>=array[left]){
        
                    left = mid;
                }else{
        
                    right = mid;
                }
            }
         
          // 最后返回 mid下标的元素
          
            return array[mid];
        }
    }

# 三、奇偶互换 #

题目链接：

[https://www.nowcoder.com/practice/beb5aa231adc45b2a5dcc5b62c93f593?][https_www.nowcoder.com_practice_beb5aa231adc45b2a5dcc5b62c93f593]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
  大家做这种题目一定要看好，调换奇数和偶数的时候 ，有没有说明 相对位置是否发生改变.

当然了，这道题原题是不需要保证奇偶位置不变的，先给大家说一下 相对位置发生改变的题目.

## 相对位置变化 ##

**思路**

给大家说一下思路：

> 左右指针法

> 我们需要定义一个 左指针 和右指针 分别从 数组的两头进行遍历.

> 在一个 left < right 的一个循环条件下，  
> 左指针从数组的左边开始遍历，遇到偶数就停止，遇到奇数就跳过  
> 右指针从数组的右边开始遍历，遇到奇数就停止，遇到偶数就跳过.

> 这两边遍历完之后我们会得到 左边遍历得到的偶数下标 ，右边遍历得到的奇数下标，此时交换这两个下标的数字

> 重复以上操作，我们最后得到了一个 奇数在前 偶数在后 (相对位置发生变化) 的 一个数组序列.

**题解代码**

import java.util.* ;
    
    // 这是相对位置发生变化的一种做法
    public class Solution {
        
    
        public void reOrderArray(int [] array) {
        
           if(array == null || array.length == 0){
        
               return;
           }
            
            // 定义一个左右指针
            int left = 0;
            int right = array.length-1;
            
            // 分别从数组的两头开始遍历
            while(left<=right){
        
            
    // 从左边开始遍历 ，遇到偶数停止，遇到奇数跳过
    
                while(left<right && array[left]%2 ==1){
        
                    left++;
                }
                
    // 从右边开始遍历 ，遇到奇数停止，遇到偶数跳过
    
                while(left<right && array[right]%2 == 0){
        
                    right--;
                }
                
         // 此时我们得到了一个左边是偶数的下标，右边是奇数的下标
         // 交换奇数 偶数的排列顺序
         
         	if(left <= right){
        
    	         int tmp = array[left];
                 array[left] = array[right];
                 array[right] = tmp;
    
       	    }
              
                
            }
            
        }
    }

## 相对位置不变 ##

**思路**

> 从左向右，每次遇到的，都是最前面的奇数，一定将来要被放在k下标处,

> 现将当前奇数保存起来

> 将该奇数之前的内容（偶数序列）,整体向后移动一个位置.

> 将奇数保存在它将来改在的位置下标（k指向的位置），因为我们是从左往右放的，没有跨越奇 数，所以一定是相对位置不变的

import java.util.* ;
    
    public class Solution {
        
        public void reOrderArray(int [] array) {
        
           if(array == null || array.length == 0){
        
               return;
           }
            
            int k = 0;
            
            for(int i = 0;i<array.length;i++){
        
                if(array[i]%2 == 1){
        
                    
                    int tmp = array[i];
                   for(int j = i-1;j>=k;j--){
        
                       array[j+1] = array[j];
                   }
                           
                   array[k++]  = tmp;
                }
    
            }
            
        }
    }

# 四、数组中出现次数超过一半的数字 #

题目链接：

[https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?][https_www.nowcoder.com_practice_e8a1b01a2df14cb2b228b30ee6a92163]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 4]

## 思路一 ##

> 思路一：定义map，使用<数字，次数>的映射关系，最后统计每个字符出现的次数

**相关代码**

import java.util.*;
    
    public class Solution {
        
    
        public int MoreThanHalfNum_Solution(int [] array) {
        
        
             Map<Integer ,Integer> map = new HashMap<>();
            
            for(int i =0;i<array.length;i++){
        
                if(map.get(array[i]) == null){
        
                    // 如果这个 arr[i] 没有在 map 中出现过的话，那么就往 map 中 存上arr[i],且计数为1
                    map.put(array[i],1);
                }else{
        
                    // 这种情况是 arr[i] 出现的次数大于1次，出现很多次
                    int k = map.get(array[i]);
                    // 我们先 用 k 来保存这个arr[i] 在map中之前出现的次数
                    map.put(array[i],k+1);
                    // arr[i] 存放入 map中，并且次数+1
                }
                
                if(map.get(array[i])>array.length/2){
        
    //                 如果arr[i] 在 map 中出现的次数超过数组长度的一半，那么直接返回 arr[i]
                    return array[i];
                }
            }
            
            // 因为数组中可能0出现次数超过长度一半，这里是为了符合逻辑，并不是真正的业务代码.
            return 0;
            
        }
    }

## 思路二 ##

> 思路二： 排序，出现次数最多的数字，一定在中间位置。然后检测中间出现的数字出现的次数是否符合要求

**相关代码**

import java.util.*;
    
    public class Solution {
        
        public int MoreThanHalfNum_Solution(int [] array) {
        
           if(array == null || array.length == 0){
        
               return 0;
           }
            
            // 我们先将这个数组进行排序，我们可以 用到几种排序方法： 直接插入排序、堆排序、冒泡排序、选择排序等等
            for(int i =0;i<array.length;i++){
        
               for(int j = 0;j<array.length-1-i;j++){
        
                   if(array[j]>array[j+1]){
        
                       int tmp = array[j];
                       array[j] = array[j+1];
                       array[j+1] = tmp;
                   }
               }    
            }
            
    //         如果这个数字出现的次数超过了数组长度的一半，那么数组最中间的那个数字一定是 我们想要得到的数字
            int left = 0;
            int right = array.length-1;
            int mid = (left+right)/2;
            int count = 0;
            
            
            for(int i = 0;i<array.length;i++){
        
                if(array[i] == array[mid]){
        
                    count++;
                }
            }
            
    //         如果中间的数字出现的次数大于 数组长度的一半，那么返回这个数字，
    //         如果没有，那么返回0(同样的，0也只是逻辑上的处理，并不是业务的处理）
            return count>array.length/2 ? array[mid] : 0;
            
        }
    }

## 思路三 ##

> 思路三：目标条件：目标数据超过数组长度的一半，那么对数组，我们同时去掉两个不同的数字，到最后剩下的一个数就是该数字。如果剩下两个，那么这两个也是一样的，就是结果），在其基础上把最后剩下的一个数字或者两个回到原来数组中，将数组遍历一遍统计一下数字出现次数进行最终判断。

**相关代码**

import java.util.*;
    
    public class Solution {
        
        public int MoreThanHalfNum_Solution(int [] array) {
        
           if(array == null || array.length == 0){
        
               return 0;
           }
            
         int times = 1;
         int target = array[0];
         
    //         下面这个过程很难理解
            
    //         每两个不同的数字 会抵消一次 times
            
    //         如果times == 0，那么说明i之前的数字 都不同，再次更换一个 target
            
    //         到最后 target 保留的数字很可能是 出现次数超过数组长度一半的数字
            
            
            for(int i = 1;i<array.length;i++){
        
                if(times ==0){
        
              //  如果 times 为0，那么之前不同的抵消完了
                    target = array[i];
                    times = 1;
                }else if(array[i] == target){
        
                    times++;
                }else{
        
                    times--;
                }
            }
        
         //   如果输入本身符合条件，那么最后 times 大于0，target 保存的目标就是准目标，但是还需要确认
    
        int count = 0;
        for(int i = 0;i<array.length;i++){
        
            if(target == array[i]){
        
                count++;
            }
        }
        
        return count>array.length/2? target: 0;
        
            
        }
    }

好了，今天的内容就结束了，希望大家多多练习~~

**谢谢欣赏！！！**

[https_www.nowcoder.com_practice_abc3fe2ce8e146608e868a70efebf62e]: https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/cf64afbceac143569e16465c3c6760c5.png
[https_www.nowcoder.com_practice_9f3231a991af4f55b95579b44b7a01ba]: https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/c828048dbd0842bc8110101ebd03871e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/019672402b394d6c9d8fe6c40105f028.png
[https_www.nowcoder.com_practice_beb5aa231adc45b2a5dcc5b62c93f593]: https://www.nowcoder.com/practice/beb5aa231adc45b2a5dcc5b62c93f593?
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/68f83cc770cc461f88d3a41187161efe.png
[https_www.nowcoder.com_practice_e8a1b01a2df14cb2b228b30ee6a92163]: https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUkFJTiA3_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/754824373bdb4b838592eb84837f79b2.png