16.最接近的三数之和 && 数组排序(默认升)

1.知识点:

  • 双指针
  • 数组排序(默认升序);自定义降序

2.排序代码

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
39
40
41
42
43
44
45
46
47
48
49
50

/*
* Java 中 实现 数组的排序
* 默认是 上升序列;
* 若要 下降,则默认需要 Integer 或者 Float 等 "类"类型,不能使用基础类型;
*
* */
import java.util.*;

public class 最接近的三数之和_16 {
public static void main(String[] args) {
//注意,要想改变默认的排列顺序,不能使用基本类型(int,double, char),而要使用它们对应的类
Integer[] arr = {9, 8, 7, 2, 3, 4, 1, 0, 6, 5};
//定义一个自定义类MyComparator的对象
//法一:实现降序;需要类型,不能是基础类型
// Arrays.sort(arr,Collections.reverseOrder());
//法二:实现降序
// Arrays.sort(arr, (a,b) -> (b - a));

//法三:需要自己重写 Comparator
Comparator cmp = new MyComparator();
Arrays.sort(arr, cmp);
for (int x : arr) {
System.out.print(x + " ");
}

//若得到的是 int ,需要先手动转为 Integer 类型!
int scores[] = new int[]{1,2,3,89,4};
Integer newScores[] = new Integer [5];
for(int i=0;i<scores.length;i++){
// newScores[i]= new Integer(scores[i]);
newScores[i] = scores[i];
}
System.out.println();

Arrays.sort(newScores,Collections.reverseOrder());
for (int x : newScores) {
System.out.print(x + " ");
}

}
}

//实现Comparator接口
class MyComparator implements Comparator<Integer> {
@Override //作用是检查下面的方法名是不是父类中所有的,也起到注释的作用
public int compare(Integer a, Integer b) {
return a > b ? -1 : 1;
}
}
  • 注意点:

  • Collections.reverseOrder()
    <!--1-->
    
    * 道理同上
  • 自己重写 Comparator
    <!--2-->
    
    才可以实现 用 int 类型直接排序(默认是升序列)
  • 若要降序,基本都需要 Integer 类型;

  • 若是 int 基础类型,那么需要手动 转换一下类型;


3.题目:

寻找数组中三个数字之和,要求和最接近于目标数值

image-20200624135415119

  • 法一:暴力:O($N^3$)

  • ```java
    //法一:暴力 O(n^3)
    int best = 100000;
    int diff = 100000;
    for(int i=0;i<nums.length;i++){

    for(int j = i+1;j<nums.length;j++){
        for(int k = j+1;k<nums.length;k++){
            if(Math.abs(nums[i]+nums[j]+nums[k] - target) < diff){
                diff = Math.abs(nums[i]+nums[j]+nums[k] - target);
                best = nums[i]+nums[j]+nums[k];
            }
        }
    }

    }
    return best;

    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
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57

    *

    * 法二:双指针:第一个元素从头到尾遍历,二、三元素从表头、尾向中间靠拢。

    * 好处是:省掉了很多没必要的不可能组合;(有点剪枝的意思了)

    ```java
    import java.util.*;

    public class 最接近的三数之和_16 {
    public static void main(String[] args) {
    }
    public int threeSumClosest(int[] nums, int target){
    Arrays.sort(nums);//升序排列
    int n = nums.length;
    int best = 10001000;

    for(int i = 0;i < n; i++){
    //若下一个元素和当前元素内容一样,则可以跳过;
    //continue,直接跳过当前循环,进入下一次循环;
    if(i>0 && nums[i] == nums[i-1]){
    continue;
    }

    //使用双指针,枚举 b 和 c;
    int j = i+1, k = n-1;
    while(j < k){
    int sum = nums[i] + nums[j] + nums[k];
    //如果直接等于target,那么直接返回,最接近;
    if(sum == target){
    return target;
    }
    if(Math.abs(sum - target) < Math.abs(best - target)){
    best = sum;
    }
    if(sum > target){
    int k0 = k - 1;
    //开始移动 c 的指针,直到比原本的 c 值要小;
    // 向左移动到下一个不想等的元素;
    while(j < k0 && nums[k0] == nums[k]){
    --k0;
    }
    k = k0; // 如果发生 k = k0 == j;那么会退出现在的 while(j < k)
    }else{
    //如果 sum < target,那么就把 b 指针向左移动;
    int j0 = j+1;
    while(j0 < k && nums[j0] == nums[j]){
    ++j0;
    }
    j = j0;
    }
    }
    }
    return best;
    }
    }