Lc33---- 414. 第三大的数(java版)---排序(去重复制到新数组)

admin2024-05-15  0

1.题目描述
给你一个非空数组,返回此数组中 第三大的数 。如果不存在,则返回数组中最大的数。

示例 1:

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

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

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

2.思路
(1)去重思路
循环确实是从1开始的。这是因为该循环用于去重,通过比较当前元素与前一个元素是否相同来实现。这种方法会导致遗漏数组中的第一个元素。所以,为了确保第一个元素也被考虑到,循环从索引1开始。

在这段代码中,通过将不同的元素移到数组的前面来去除重复。因此,数组的前面部分将存储去重后的元素。count 记录的是去重后的数组的长度,所以在处理去重时,count 的起始值为1,而不是0。

虽然这种方法会导致遗漏第一个元素,但由于排序后数组的第一个元素肯定是最小的,因此不会影响第三大的数的计算。
(2)在这个循环中,我们不需要遍历数组中的第一个元素(即 nums[0]),因为它没有前一个元素。我们从数组的第二个元素开始(即 nums[1])进行比较,以确保每个元素都能被正确地检查和处理

3.代码实现

class Solution {
    public int thirdMax(int[] nums) {

        Arrays.sort(nums);
        int cnt=1;//新数组的起始长度
         //数组索引从0开始,终止条件是nums.length-1
        for(int i=1;i<=nums.length-1;i++)
        {  //如果当前元素和前一个元素不一样,则将旧数组的该元素,添加到新数组里面
           //如果当前元素和前一个元素一样,则不处理。
            if(nums[i]!=nums[i-1])
            {
              nums[cnt]=nums[i];
              cnt++;
            }
        }
           if(cnt<3)
           {
            return nums[cnt-1];
            //newNUms[1,2],cnt的值是2
            //所以返回当前最大的元素 ,也就是cnt-1=1,就是newNums[1],数组索引从0开始,所以最后一个数的索引是cnt-1
           }
           
           ///否则,cnt>=3
           return nums[cnt-3];
           //设去重后的数组 newNums 为 [1, 2, 3, 4, 5, 6],那么 count 的值为6。第三大的数就是数组倒数第三个元素,即 newNums[6 - 3],也就是 newNums[3],其值为3,正是我们期望的结果。
            

    }
}
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!