数组系列——数组的遍历

57 阅读 0 评论 38 点赞

我是靠谱客的博主故意冬瓜，最近开发中收集的这篇文章主要介绍数组系列——数组的遍历，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

895.最大连续的1.

给定一个二进制数组，计算其中最大连续 1 的个数。

示例：

输入：[1,1,0,1,1,1]
输出：3
解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/max-consecutive-ones
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

1.找到第一个1的位置 a [ i ]

2. a [ i ] 是否== a [ i+1 ] （等于的话返回 count，不等于的话开始找第二个1的位置，同时返回max。）

3.重复第二步

4.如果第二个max比第一个大，那么就返回新的max

class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int max = 0; int count = 0;
for(int i=0;i<nums.length;i++){
if(nums[i]==1) count++;
else{
if(count>max)max=count;
count = 0;
}
}
if(count>max)max=count;
return max;
}
}

关于代码优化：else这里是nums [ i ] == 0 的情况，这样就会导致一种情况，也就是如果最后一个元素是1的话，那就不会返回一个新的max值。所以才需要在for循环之外加一个if判断语句。

优化的话，在参考leetcode评论的基础上，可以把else去掉，这样就可以一并去掉for循环之外的判断语句。

时间复杂度是O(n),空间复杂度是O(1)

通过leetcode评论的研究，我发现还有利用双指针写的方法

class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
if(nums.length == 0) return 0;
int fast = 0,slow = 0;
int num = 0;
while(fast < nums.length){
if(nums[fast]==0) {
num = (fast - slow) > num ? fast - slow : num ;
slow = fast + 1;
fast++;
}else{
fast++;
}
}
num = (fast - slow) > num ? fast - slow : num ;
return num;
}
}

这里把方法写在这里，也值得看一看。这个思路在写题目的一瞬间，脑子里也想到了，就是找数组中0的位置，然后用0的位置减去前一个0的位置，进行比较。

495.提莫攻击

在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。

当提莫攻击艾希，艾希的中毒状态正好持续 duration 秒。

正式地讲，提莫在 t 发起发起攻击意味着艾希在时间区间 [t, t + duration - 1]（含 t 和 t + duration - 1）处于中毒状态。如果提莫在中毒影响结束前再次攻击，中毒状态计时器将会重置，在新的攻击之后，中毒影响将会在 duration 秒后结束。

给你一个非递减的整数数组 timeSeries ，其中 timeSeries[i] 表示提莫在 timeSeries[i] 秒时对艾希发起攻击，以及一个表示中毒持续时间的整数 duration 。

返回艾希处于中毒状态的总秒数。

示例 1：

输入：timeSeries = [1,4], duration = 2
输出：4
解释：提莫攻击对艾希的影响如下：
- 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
- 第 4 秒，提莫再次攻击艾希，艾希中毒状态又持续 2 秒，即第 4 秒和第 5 秒。
艾希在第 1、2、4、5 秒处于中毒状态，所以总中毒秒数是 4 。
示例 2：

输入：timeSeries = [1,2], duration = 2
输出：3
解释：提莫攻击对艾希的影响如下：
- 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
- 第 2 秒，提莫再次攻击艾希，并重置中毒计时器，艾希中毒状态需要持续 2 秒，即第 2 秒和第 3 秒。
艾希在第 1、2、3 秒处于中毒状态，所以总中毒秒数是 3 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/teemo-attacking
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

返回中毒的总秒数

1.设两个变量时间总数和每轮要加的数量

2.对数组timeSeries进行一次for循环遍历

3.如果两个元素值的差比duration大，就返回duration作为加的数量

4.如果元素值的差比duration小，就返回元素差作为加的数量

5.最后return的值需要加上一个duration（因为最后一个元素的情况没有考虑进去）

class Solution {
public int findPoisonedDuration(int[] timeSeries, int duration) {
int timeSum = 0;
int timeAdd = duration;
for(int a=0;a<timeSeries.length-1;a++){
if(timeSeries[a]+duration>timeSeries[a+1]) {
timeAdd=timeSeries[a+1]-timeSeries[a];
timeSum=timeSum+timeAdd;
}
else {timeAdd=duration;timeSum=timeSum+timeAdd;
}
}
return timeSum+duration;
}
}

leetcode的方法1

每次比较元素差与duration的大小，小的返回为加的值。（极其巧妙）

class Solution {
public int findPoisonedDuration(int[] timeSeries, int duration) {
if (timeSeries.length == 1) {
return duration;
}
int ans = 0;
for (int i = 0; i < timeSeries.length - 1; i++) {
ans += Math.min(timeSeries[i + 1] - timeSeries[i], duration);
}
return ans + duration;
}
}

leetcode的方法2

先假设中毒时间拉满，然后减去重复的时间即可。


public int findPoisonedDuration(int[] timeSeries, int duration) {
int res = timeSeries.length * duration;
for(int i = 1; i < timeSeries.length; i++){
if(timeSeries[i] - timeSeries[i-1] < duration){
res -=
duration - timeSeries[i] + timeSeries[i-1];
}
}
return res;
}

414.

给你一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。

示例 1：

输入：[3, 2, 1]
输出：1
解释：第三大的数是 1 。
示例 2：

输入：[1, 2]
输出：2
解释：第三大的数不存在, 所以返回最大的数 2 。
示例 3：

输入：[2, 2, 3, 1]
输出：1
解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/third-maximum-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

1.首先将数组进行排序，从小到大进行排序（这里理想状态下应该是从大到小）

2.for循环对数组进行遍历

3.比较nums[ i ]与num[ i-1 ]的大小

4.当相等的情况达到两次后，返回num[ i-1 ]

class Solution {
public int thirdMax(int[] nums) {
Arrays.sort(nums);
for(int i =nums.length-1,j =1;i>0;i--){
if(nums[i]!=nums[i-1]){
j++;
if(j==3) return nums[i-1];
}
}
return nums[nums.length-1];
}
}

628.

给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

示例 1：

输入：nums = [1,2,3]
输出：6
示例 2：

输入：nums = [1,2,3,4]
输出：24
示例 3：

输入：nums = [-1,-2,-3]
输出：-6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-of-three-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

1.先将数组进行排序，因为要找出三个数的最大乘积

2.如果数组排序后最大的那个数小于等于0，那么最大值就等于最后三个数相乘

3.如果数组排序后最大的那个数大于0，有以下两种情况：

（1）最大值=最后一个数乘以两个最小的负数

（2）最大值=最后三个数（皆为正数）相乘

4.完成算法

class Solution {
public int maximumProduct(int[] nums) {
int length = nums.length-1;
Arrays.sort(nums);
if(nums[length]>0)
{
int max =nums[length]*nums[length-1]*nums[length-2];
int min =nums[0]*nums[1]*nums[length];
return Math.max(max,min);
}
else{
return nums[length]*nums[length-1]*nums[length-2];
}
}
}

进行优化：

可以去掉if else这个情况判断，因为无论怎么比较，其实就是两种情况1---最后两个负数乘以最大的那个数 2---最大的三个数相乘

直接进行数学方法判断

class Solution {
public int maximumProduct(int[] nums) {
int length = nums.length-1;
Arrays.sort(nums);
int max =nums[length]*nums[length-1]*nums[length-2];
int min =nums[0]*nums[1]*nums[length];
return Math.max(max,min);
}
}

时间复杂度O(nlogn) ，空间复杂度O(logn)

leetcode评论中看到的方法：一次遍历

class Solution {
public int maximumProduct(int[] nums) {
// 最小的和第二小的
int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
// 最大的、第二大的和第三大的
int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
for (int x : nums) {
if (x < min1) {
min2 = min1;
min1 = x;
}
else if (x < min2) {
min2 = x;
}
if (x > max1) {
max3 = max2;
max2 = max1;
max1 = x;
} else if (x > max2) {
max3 = max2;
max2 = x;
} else if (x > max3) {
max3 = x;
}
}
return Math.max(min1 * min2 * max1, max1 * max2 * max3);
}
}

需要知道的新知识：if……else if ，每一个else都应有对应的if相配对，一个 if……else if为一个组合。

if (x < min1) {
min2 = min1;
min1 = x;
}
else if (x < min2) {
min2 = x;
}

这一段的意思是：如果 x<min1不成立，就执行else if（），如果成立就不执行。

其等于以下的代码

  if(x<min2){

                if(x<min1){

                    min2 = min1;

                    min1 = x;

                }

                else min2 = x;

            }

其实是一个if else if的组合，第二个if组合也是如此。

此为重写后的等价代码

class Solution {
public int maximumProduct(int[] nums) {
// 最小的和第二小的
int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
// 最大的、第二大的和第三大的
int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
for (int x : nums) {
if (x < min2) {
if (x < min1) {
min2 = min1;
min1 = x;
} else min2 = x;
}
if (x > max3) {
if (x > max2) {
if (x > max1) {
max3 = max2;
max2 = max1;
max1 = x;
} else {
max3 = max2;
max2 = x;
}
} else max3 = x;
}
}
return Math.max(min1 * min2 * max1, max1 * max2 * max3);
}
}

至此，做完了刷题系列的第一个系列数组——数组的遍历

对应的leetcode题目是485、495、414、628