落风的风
0%

leetcode数组（05）

Posted on Edited on In

189 旋转数组
495 提莫攻击
414 找第三大的数

#189 旋转数组

一道难度中等的题，我只能想到暴力解法

暴力解法

即将一次转移一个元素到旋转 k 次，每次将数组旋转 1 个元素。数组更新的次数过多、效率低下。

时间复杂度：O(n*k) 。每个元素都被移动 1 步（O(n)O(n)） k次（O(k)O(k)。

空间复杂度：O(1)。没有额外空间被使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public void rotate(int[] nums, int k) {
        k=k%nums.length;
        int temp =0;
        for (int i=1;i<=k;i++){
            temp = nums[nums.length-1];
            for (int j = nums.length-1;j>=1;j--){
                nums[j]=nums[j-1];
            }
            nums[0]=temp;
        }
    }
}

使用反转方法

  • 我的程序
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
class Solution {
    public void rotate(int[] nums, int k) {

        int length=nums.length;
        k=k%length;
        inverse(nums,0,length-1);
        inverse(nums,0,k-1);
        inverse(nums,k,length-1);
    }

    public int[] inverse(int[]nums ,int start,int end){
        if (start>end){
            return nums;
        }
        int k=(end-start+1)/2>1?(end-start+1)/2-1:0;
        for (int i=0; i<=k; i++){
            int temp = nums[i+start];
            nums[i+start]=nums[end-i];
            nums[end-i]=temp;
        }
        return nums;

    }

}
  • 官方解答、很优雅
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

# 495 提莫攻击

一道简单的中等难度题，思路也清晰，遍历一遍数组，在每个时间节点判断中毒状态的时间如何增加：如果中毒时间已过就再加上一个持续时间；如果持续时间没过就加上距离上一次中毒到这一次中毒的时间间隔。

思路和官方一致，题解区好像也没有更好的解答。

#414 找第三大的数

这题我花了快一个小时，时间复杂度最大是O(4n)，我的思路是借鉴485题那个滑动窗口的方法，4个窗口向后滑动，先剔除重复的数、再剔除最小的数。

代码很长，我很辣鸡，这我知道。时间复杂度打败40%，空间复杂度打败75%。

现在网也不行了，看不了题解，卒。B站、微博都能进，力扣网炸了，难道菜鸡们都在晚上刷题？

我的解答

神乎其技，虽然菜、也算是举一反三吧

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
public static int thirdMax(int[] nums) {
    int length = nums.length;
    if (length==1){
        return nums[0];
    }
    if (length==2){
        return Math.max(nums[0],nums[1]);
    }
    if(length>3) {
        for (int r = 2; r <= length - 2; r++) {
            //先看4格窗口中是否有重复的数出现 有就前置交换
            if (nums[r - 2] == nums[r - 1] || nums[r - 2] == nums[r] || nums[r - 2] == nums[r + 1]) {
                continue;
            }
            if (nums[r - 1] == nums[r] || nums[r - 1] == nums[r + 1]) {
                nums[r - 1] = nums[r - 2];
                continue;
            }
            if (nums[r] == nums[r + 1]) {
                nums[r] = nums[r - 2];
                continue;
            }
            //没有重复的 就把最小的前置交换
            int min = nums[r - 2];
            int indmin = r - 2;
            for (int i = -2; i <= 1; i++) {
                if (nums[r + i] < min) {
                    min = nums[r + i];
                    indmin = r + i;
                }
            }
            nums[indmin] = nums[r - 2];
        }
        nums[0]=nums[length-3];
        nums[1]=nums[length-2];
        nums[2]=nums[length-1];
    }
    //相当于数组只剩下3个数
    if (nums[0]==nums[1]||nums[0]==nums[2]||nums[1]==nums[2]){
        return Math.max(Math.max(nums[0],nums[1]),Math.max(nums[0],nums[2]));
    }else{
        return Math.min(Math.min(nums[0],nums[1]),Math.min(nums[0],nums[2]));
    }
}

扣友题解

  • 思路一： 借用TreeSet（红黑树）；时间复杂度：O(n * log3) == O(n) 比较好想的思路

    1、维护一个只有3个元素的TreeSet，如果大于三个元素就就把Set中的最小最小值remove掉。
    2、最后如果Set中元素小于3就返回Set最大值，否则返回最小值。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int thirdMax(int[] nums) {
        TreeSet<Integer> set = new TreeSet<>();
        for (Integer elem : nums) {
            set.add(elem);
            if (set.size() > 3) set.remove(set.first());
        }
        return set.size() < 3 ? set.last() : set.first();   // set.last() 里面最大的元素
    }
}
作者：happy_yuxuan

点评：这个思路其实和我的出奇一致，扣友用TreeSet来去重，遍历数组将最小的元素remove掉。但是大佬用了不到10行，我用超过40行，这就是技术的区别啊。不过现阶段思路更重要、技术多练就好。

  • 思路二：

1、用三个变量来存放第一大，第二大，第三大的元素的变量，分别为one, two, three；
2、遍历数组，若该元素比one大则往后顺移一个元素，比two大则往往后顺移一个元素，比three大则赋值个three；
3、最后得到第三大的元素，若没有则返回第一大的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int thirdMax(int[] nums) {
        long first = Long.MIN_VALUE;
        long second = Long.MIN_VALUE;
        long third = Long.MIN_VALUE;
        for (int num : nums) {
            if(num>first){
                third = second;
                second = first;
                first = num;
            }else if(num>second&&num<first){
                third = second;
                second = num;
            }else if(num<second&&num>third){
                third = num;
            }
        }
        return third!=Long.MIN_VALUE ? new Long(third).intValue() : new Long(first).intValue();
    }
}

作者：liccil76
-------------感谢阅读没事常来-------------