leetcode-697-Degree of an Array

题目描述:

Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

Example 1:

Input: [1, 2, 2, 3, 1]
Output: 2
Explanation: 
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.

Example 2:

Input: [1,2,2,3,1,4,2]
Output: 6

Note:

  • nums.length will be between 1 and 50,000.
  • nums[i] will be an integer between 0 and 49,999.

要完成的函数:

int findShortestSubArray(vector<int>& nums) 

说明:

1、给定一个非空vector,里面含有非负数,vector的程度定义为“其众数出现的频率”,想找到一个尽可能短的连续子vector,使得该子vector的程度和vector的程度一样。

2、直接的想法,使用unordered_map遍历一遍vector,统计vector中元素出现的次数,然后再遍历一遍unordered_map找到出现最多次的元素(可能有多个),然后在vector中找到该元素的首次出现index和最后一次的index,得到长度。如果有多个元素,这里要求出最短的长度。

暴力解决,代码如下:(附解释)

    int findShortestSubArray(vector<int>& nums) 
    {
        unordered_map<int,int>chuxian;
        vector<int>elem;
        int s1=nums.size();
        int max1=0;
        for(int i=0;i<s1;i++)//存储各个元素的出现次数
        {
            if(chuxian.count(nums[i]))
                chuxian[nums[i]]++;
            else
                chuxian[nums[i]]=1;
        }
        for(unordered_map<int,int>::iterator iter=chuxian.begin();iter!=chuxian.end();iter++)
        {//遍历map找到出现最多次的元素,插入到新定义的vector中
            if(iter->second>max1)
            {
                elem.clear();
                elem.push_back(iter->first);
                max1=max(max1,iter->second);
            }
            else if(iter->second==max1)
                elem.push_back(iter->first);
        }
        int i,j,t,min1=INT_MAX,s2=elem.size(),k=0;
        while(k<s2)//每个元素都求出对应的长度,最后得到最短的长度
        {
            i=0;
            j=s1-1;
            t=elem[k];
            k++;
            while(i<s1)
            {
                if(nums[i]==t)
                    break;
                i++;
            }
            while(j>=0)
            {
                if(nums[j]==t)
                    break;
                j--;
            }
            min1=min(min1,j-i+1);
        }
        return min1;
    }

上述代码实测109ms,beats 12.33% of cpp submissions。

3、改进:

上述代码实在太慢了,我们要先遍历vector,找到元素和元素出现次数的对应关系

接着再遍历map,由最大的元素出现次数找到元素

接着再遍历vector,找到元素的首index和末index。

我们可不可以直接把第三步要做的事情在第一次遍历中就给实现了,又不耽误元素出现次数的统计。

我们可以把元素出现的位置,作为一个vector,插入map的second中,这样就可以了。

代码如下:(附解释)

    int findShortestSubArray(vector<int>& nums) 
    {
        unordered_map<int,vector<int>> m1;//第二项是个vector
        for(int i=0;i<nums.size();i++) 
            m1[nums[i]].push_back(i); //统计元素的出现位置
        int max1=INT_MIN;
        for(auto iter=m1.begin();iter!=m1.end();iter++) //遍历map找到出现的最多次数
            max1=max(max1,int(iter->second.size()));//degree就是max1
        int min1=INT_MAX;
        for(auto iter=m1.begin();iter!=m1.end();iter++)//遍历map找到对应的元素,计算最短长度
        {
            if(iter->second.size()==max1)//
                min1=min(min1,iter->second.back()-iter->second[0]+1);
        }
        return min1;
    }

上述代码实测33ms,beats 97.23% of cpp submissions。

这里要感谢leetcode用户@sguox002在讨论区分享的代码,提供了新的思路。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏文武兼修ing——机器学习与IC设计

JavaScript入门笔记(2)字符串相关列表对象

字符串相关 字符串基础 字符串历来是各种编程语言坑最多的地方(个人认为),不同软件语言在字符串上的操作的差别比软件语言和硬件描述语言的差距都大(一样是个人认为)...

3156
来自专栏Kevin-ZhangCG

[ Java学习基础 ] Java异常处理

3126
来自专栏Java后端技术

Java Collection、Map集合总结

      依赖hashCode()和equals()两个方法进行保证元素唯一性,开发中使用开发工具自动生成就好。

822
来自专栏java学习

java每日一练(2017/9/16)

本期题目 (单选题) 1、代码String str=”123456a”;int i=Integer.parseInt(str);会报异常的是() A java...

3778
来自专栏老马说编程

(18) 为什么说继承是把双刃剑 / 计算机程序的思维逻辑

继承是把双刃剑 通过前面几节,我们应该对继承有了一个比较好的理解,但之前我们说继承其实是把双刃剑,为什么这么说呢?一方面是因为继承是非常强大的,另一方面是因为...

2496
来自专栏Java架构

面试必备:30 个 Java 集合面试问题及答案

Java集合框架为Java编程语言的基础,也是Java面试中很重要的一个知识点。这里,我列出了一些关于Java集合的重要问题和答案。

782
来自专栏小樱的经验随笔

【正则表达式学习笔记之一】简单认识正则表达式

一、引言   正则表达式是什么东东?   在编写处理字符串的程序或网页时,经常会有查找符合某些复杂规则的字符串的需要。正则表达式就是用于描述这些规则的工具。换句...

2093
来自专栏梦魇小栈

重新介绍 JavaScript(JS全面系列教程)

为什么会有这一篇“重新介绍”呢?因为 JavaScript 堪称世界上被人误解最深的编程语言。虽然常被嘲为“玩具语言”,但在它看似简洁的外衣下,还隐藏着强大的语...

1572
来自专栏有趣的Python

3-Linux C语言结构体-学习笔记

将#include <stdio.h>中stdio.h展开,将未注释的内容直接写入.i文件。

2871
来自专栏落影的专栏

程序员进阶之算法练习(三十二)LeetCode专场

题目链接 题目大意: 给出一个链表RandomListNode *next, *random; 每个节点有int值,有两个指针,一个指向下一个节点,一个指...

922

扫码关注云+社区

领取腾讯云代金券