技巧

天前	#287 寻找重复数	中等	2 次
2 天前	#31 下一个排列	中等	3 次
2 天前	#75 颜色分类	中等	1 次
2 天前	#169 多数元素	简单	4 次
2 天前	#136 只出现一次的数字	简单	2 次

# 只出现一次数字

class Solution {
    public int singleNumber(int[] nums) {
        int res = nums[0];
        for(int i =1; i< nums.length; i++){
            res^=nums[i];
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9

# 多数元素

class Solution {
    public int majorityElement(int[] nums) {
        if(nums.length == 1){
            return nums[0];
        }
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i< nums.length; i++){
            if(map.containsKey(nums[i])){
              int val =   map.get(nums[i]);
              if(val+1 > nums.length/2){
                  return nums[i];
              } 
              map.put(nums[i], val+1);
            } else{
                map.put(nums[i], 1);
            }
        }
        return -1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 颜色分类

class Solution {
    public void sortColors(int[] nums) {
        quickSort(nums, 0, nums.length-1);
    }
    public static void quickSort(int[] arr, int low, int high) {
        if (arr == null || arr.length == 0) {
            return;
        }
        if (low >= high) {
            return;
        }
        int middle = low + (high - low) / 2;
        int pivot = arr[middle];
        int i = low, j = high;
        while (i <= j) {
            while (arr[i] < pivot) {
                i++;
            }
            while (arr[j] > pivot) {
                j--;
            }
            if (i <= j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }
        if (low < j) {
            quickSort(arr, low, j);
        }
        if (high > i) {
            quickSort(arr, i, high);
        }
    }
}
思路 ： 快排  直接背

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

# 下一个排序

class Solution {
    public void nextPermutation(int[] nums) {
        for(int i = nums.length-1; i>= 0; i--){
            for(int j = nums.length-1; j >= i; j--){
                if(nums[i] < nums[j ]){
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j]= temp;                    
                    Arrays.sort(nums, i+1, nums.length);
                    return;
                }
            }
        } 
        Arrays.sort(nums);   
    }
    
}
思路：
  1、倒排遍历  
  2、 if(nums[i] < nums[j ] 之后 交换位置  然后对数组对应 i+1, nums.length排序
  3、最后如果都不符合  就对整个数组排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 寻找重复数

class Solution {
    public int findDuplicate(int[] nums) {
        Arrays.sort(nums);
        int res = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                res = nums[i];
                break;
            }
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

编辑

上次更新: 2024/03/26, 9:03:00

← 多维动态规划数组 →