【剑指offer第五天】查找算法

我就是我 2022-09-04 00:49 246阅读 0赞

# 第一题 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70]  
每一行从小到大排序，每一列也是从小到大排序。因此，每一行的最后一个数就是当前行最大的数字，如果该数字比target小就进入下一行，如果比target大就将列数减一（因为当前数字往下往右都是大于该数字的，往左往上都是小于该数字的）。

class Solution { 
        public boolean findNumberIn2DArray(int[][] matrix, int target) { 
            if(matrix.length <= 0) return false;
            int l = matrix.length,r = matrix[0].length;
            int i = 0,j = r - 1;
            while(i < l&&j >= 0){ 
                if(matrix[i][j] < target){ 
                    i++;
                }else if(matrix[i][j] > target){ 
                    j--;
                }else{ 
                    return true;
                }
            }
            return false;
        }
    }

# 第二题 #

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

### 方法一 ###

找到第一个逆序的数字，如果没有说明没有进行逆序，返回第一个数字。

class Solution { 
        public int minArray(int[] numbers) { 
            int l = numbers.length;
            for(int i = 0;i < l - 1;i++){ 
                if(numbers[i + 1] < numbers[i]){ 
                    return numbers[i + 1];
                }
            }
            return numbers[0];
        }
    }

### 方法二 ###

上述方法一时间复杂度为O(n)，有序数组，考虑使用二分查找的方法。这里只比较mid和right的数值大小，因为right的值无论哪种情况都是在右排序数组中。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70 2]

class Solution { 
        public int minArray(int[] numbers) { 
            int left = 0, right = numbers.length - 1;
            while(left < right){ 
                int mid = (left + right)/2;
                if(numbers[mid] < numbers[right]){ 
                    right = mid;
                }else if(numbers[mid] > numbers[right]){ 
                    left = mid + 1;
                }else{ 
                    right--;
                }
            }
            return numbers[left];
        }
    }

# 第三题 #

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

### 方法一 ###

使用哈希表

class Solution { 
        public char firstUniqChar(String s) { 
            Map<Character,Integer> tmp = new HashMap<>();
            for(int i = 0;i < s.length();i++){ 
                char c = s.charAt(i);
                if(tmp.containsKey(c)){ 
                    tmp.put(c,2);
                }else{ 
                    tmp.put(c,1);
                }
            }
            for(int i = 0;i < s.length();i++){ 
                char c = s.charAt(i);
                if(tmp.get(c)==1){ 
                    return c;
                }
            }
            return ' ';
        }
    }

简洁版本

class Solution { 
        public char firstUniqChar(String s) { 
            HashMap<Character, Boolean> dic = new HashMap<>();
            char[] sc = s.toCharArray();
            for(char c : sc)
                dic.put(c, !dic.containsKey(c));
            for(char c : sc)
                if(dic.get(c)) return c;
            return ' ';
        }
    }

### 有序哈希表（输出第一个出现一次的字符，考虑使用有序的哈希表） ###

class Solution { 
        public char firstUniqChar(String s) { 
            Map<Character, Boolean> dic = new LinkedHashMap<>();
            char[] sc = s.toCharArray();
            for(char c : sc)
                dic.put(c, !dic.containsKey(c));
            for(Map.Entry<Character, Boolean> d : dic.entrySet()){ 
               if(d.getValue()) return d.getKey();
            }
            return ' ';
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70]: /images/20220829/c391ecfdeaa744699d1d82af660c87b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70 1]: /images/20220829/97a6b82578bf43029480c5496903b548.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70 2]: /images/20220829/00f6909d215d4b7ca0933c32b230172e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70 3]: /images/20220829/37c77160aaab47ca95b51a5d6b889d0e.png