public static int findRepeatNumber(int []nums){
      Arrays.Sort(nums);
      for(int i = 0; i< nums.length; i++){
          if(nums[i] == nums[i+1])
              return nums[i];
      }
      return -1;
  }

方法二. 把数组元素赋给新数组的索引，如果个数>1,则返回-1

public static int findRepeatNumber(int []nums){
    int[] newNum = new int[nums.length];
    for(int i : nums){
        if(++newNum[i] > 1) 
            return i;
    }
    return -1;
}

方法三. 新建Set集合，利用Set的无序不可重复性，如果不能添加此元素，说明重复，返回此元素

public static int findRepeatNumber(int []nums){
    HashSet<Integer> set = new HashSet<>();
    for(int i : nums){
        if(!set.add(i))
            return i;
    }
    return -1;
}

04，middle

二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下：

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

给定 target = 5，返回 true。

给定 target = 20，返回 false。

判空。matrix和其行列均不能为空

方法一：暴力查询。遍历二维数组，直到找到相同整数，返回true；或遍历完也没有找到，返回false。

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix)
        int rows = matrix.length;//行数
        int columns = matrix[0].length;//列数
        //遍历此二维数组
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < columns; j++){
                if(target == matrix[i][j])
                    return true;
            }            
        }
        return false;
    }
}

方法二：

思路：由此数组从左向右递增，从上向下递增的规律，比较target与右上角的数字，如果比它小(大)，则在左(右)边找，再与下一数字比较...直到找到相同整数，返回true；或遍历完也没有找到，返回false。
边界条件：遍历的行列指针i，j不能超过数组的行数rows，列数columns

public boolean findNumberIn2DArray(int[][] matrix, int target) {
       if(matrix == null|| matrix.length == 0|| matrix[0].length == 0) return false;
        int rows = matrix.length;//行数
        int columns = matrix[0].length;//列数
        //从右上角开始比较
        int i = 0, j = columns - 1;
        //边界条件
        while(i < rows && j >= 0){
            //target比此二维数组元素大,向下找，行指针++
            if(target > matrix[i][j]) i++;
            //target比此二维数组元素小,向左找，列指针--
            else if(target < matrix[i][j]) j--;
            //相等
            else return true;
        }
        return false;
        }
}

11，easy

旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。示例 1： 输入：[3,4,5,1,2] 输出：1 示例 2： 输入：[2,2,2,0,1] 输出：0

方法一：逐项查找，不考虑旋转。

public int minArray(int[] numbers) {
    int index = 0;
    for(int i = 0;i < numbers.length; i++){
        if(numbers[index] > numbers [i]){
            index = i;
        }
    }
    return numbers[index];
}

方法二：二分查找（减治思想），考虑旋转，比较nums[mid]与nums[right]。

public int minArray(int[] numbers) {
    int left = 0;
    int right = numbers.length - 1;
    while(left < right){
    int middle = (left + right) / 2;
      //中间值大于最右边的值，说明旋转之后最小数字在mid右面
        if(numbers[middle] > numbers[right]){
            left = middle + 1;
        }
      //中间值小于最右边的值，说明旋转之后最小的数字在mid或mid的左边
        //如[4,5,1⭐m,2,3] [5,1⭐,2m,3,4]
        else if(numbers[middle] < numbers[right]){
            right = middle ;
        }
      //中间值与最右边的值相等，不能判断最小数字在哪一边，可以缩小范围，right--
        else
            right--;
    }
    return numbers[right];//此时left,right指向同一数字
}

思考：为什么不能用最左边的值和middle比较？

举例：[3, 4, 5, 1, 2] 与 [1, 2, 3, 4, 5] ，此时，中间位置的值都比左边大，但最小值一个在后面，一个在前面，因此这种做法不能有效地减治。

12，middle

矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。

路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

[["a","b","c","e"],

["s","f","c","s"],

["a","d","e","e"]]

但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

示例：

输入：board = [
			   ["a","b"],
               ["c","d"]
              ],

     word = "abcd"

输出：false

方法一：回溯算法。（DFS+剪枝）

深度优先遍历矩阵中所有字符串可能性。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
剪枝：在搜索中，遇到这条路不可能和目标字符串匹配成功的情况（例如：此矩阵元素和目标字符不同、此元素已被访问），则应立即返回，称之为可行性剪枝。

public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                //找回words的第0个元素
                if(dfs(board,words,i,j,0))
                    return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        //board[i][j]表示矩阵元素，k表示字符串words的第k个元素
        //① 行或列索引越界 或 ② 当前矩阵元素与目标字符不同 或 ③ 当前矩阵元素已访问过 （③ 可合并至 ② ） 。
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word[k])
            return false;
        //字符串 word 已全部匹配，即 k = len(word) - 1 。
        if(k  == word.length- 1)
            return true;
        //将 board[i][j] 值暂存于变量 tmp ，并修改为字符 '/' ，
        // 代表此元素已访问过，防止之后搜索时重复访问。
        char temp = board[i][j];
        board[i][j] = '/';
        //从当前坐标的上下左右四个方向查找，只要有一个能查找到，就返回true
        boolean res = dfs(board, word,i + 1, j, k + 1) || dfs(board, word,i - 1, j, k + 1)|| dfs(board, word ,i ,j - 1, k + 1) || dfs(board, word, i, j + 1, k + 1);
        //恢复其本身值
        board[i][j] = temp;
        return res;
    }

21，easy

调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

示例：

输入：nums = [1,2,3,4]
输出：[1,3,2,4] 
注：[3,1,2,4] 也是正确的答案之一。

方法一：遍历数组，因为不要求数字顺序，从数组索引为0开始++ 保存奇数，从末位开始-- 保存偶数。

public int[] exchange(int[] nums) {
    int l = nums.length - 1;int m = 0;
    int[] res = new int[nums.length];
    for(int i = 0; i < nums.length; i++){
         //如果为偶数
         if(nums[i] % 2 == 0){
             res[l--] = nums[i];
         }
         else{
             res[m++] = nums[i];
         }
    }
    return res;
}

错误点：在for循环中i < l + 1的写法是错误的，因为l在循环体中会变化。

方法二：双指针left，right。若为奇数，left++;若为偶数,right--。否则nums[left]和nums[right]交换。

public int[] exchange(int[] nums) {
    int left = 0; int right = nums.length - 1;
    while(left < right){
        if(nums[left] % 2 != 0){
             left++;
         }
         if(nums[right] % 2 == 0){
             right--;
         }
         else{
             int temp = nums[left];
             nums[left] = nums[right];
             nums[right] = temp;
         }
     }
     return nums;
}

39，easy

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

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

方法一：先进行排序，若存在这样的数字，排序后一定位于数组中间位置。

public int majorityElement(int[] nums) {
//        //数组先排序再找出现次数超过数组长度一半的数字
       Arrays.sort(nums);//1, 2, 2, 2, 2, 2, 3 ,4 , 5
    //    for(int i = 0; i < nums.length; i++){
    //        if(nums[i] == nums[i + nums.length / 2] ){
    //            return nums[i];
    //        }
    //    }
    //    return -1;
        int l = nums.length;
        return nums[l/2];
   }

方法二：借助map，key保存数组元素，value保存出现次数。遍历数组元素，如果keySet中包含此元素，用map.get(key)得到此时的value，并更新(+1)，判断若此时value >= 数组长度的一半，返回此时的key；如果keySet中不包含此元素，加入map且使value为1。

public int majorityElement(int[] nums) {
    if(nums.length == 1) return nums[0];
    //用hashMap实现，key保存数组元素，value保存出现次数
    Map<Integer,Integer> map = new HashMap<>();
    int value = 0;
    for(int i = 0; i < nums.length; i++){ 
        if(!map.containsKey(nums[i])){
             map.put(nums[i], 1);
        }
        else {
            value = map.get(nums[i]);
            map.put(nums[i], value + 1);
            if(value + 1 > nums.length / 2) {
                return nums[i];
            }
        }
    }
    return -1;
}

57，easy

和为s的两个数字

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]

示例 2：

输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]

方法一：左右双指针。

如果两指针指向数字和 = target，返回这个数字构成的数组。
... < .... ，left 向右移。
... > .... ，right 向左移。

public int[] twoSum(int[] nums, int target) {
    int left = 0; int right = nums.length - 1;
    if(nums[left] >= target) return new int[0];
    while(nums[right] > target){
         right--;
    }
    while(left < right){
        if(nums[left] + nums[right] == target) return new int[]{nums[left], nums[right]};
        else if(nums[left] + nums[right] > target) right--;
        else left++;  
    }
    return new int[0];
}

注意： 数组遍历都可以用双指针想一想

双指针固定套路：while(left < right)

if判断中先判断 == 再判断 < , >，有助于减少运行时间

方法二：利用set的不可重复性，遍历数组将数组元素添加到set，如果set包含target - i，则返回两个元素构成的数组。

public int[] twoSum(int[] nums, int target) {
	Set<Integer> set = new HashSet<>();
    for (int i : nums) {
         set.add(i);
         if (set.contains(target - i)) {
             return new int[]{i, target - i};
         }
    }
    return new int[0];
}

------ 本文结束感谢您的阅读 ------