Degree of an Array


  • 0

    Click here to see the full article post


  • 0
    W
    This post is deleted!

  • 0
    W
    This post is deleted!

  • 0
    C

    i think it's much better to use a hashmap<Integer, List<Integer>>, where value of map store all the indexes of current num, the size of list appears to be the frequency.
    and the list.get(list.size()-1) - list.get(0) appear to be the length


  • 0
    S
    This post is deleted!

  • 0
    P

    Can I get the solutions of weekly contests in C++ too ?


  • 0
    S
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 0
    V

    Here I add the scala implementation with same approach:
    '
    def findShortestSubArray(nums: Array[Int]): Int = {
    var leftmap = MapInt, Int
    var rightmap = MapInt, Int
    var countmap = MapInt, Int

        var i: Int = 0
        for (i <- 0 until nums.length) {
            val num = nums(i)
            if (!leftmap.contains(num)) leftmap += (num -> i)
            rightmap += (num -> i)
            countmap += (num -> (countmap.getOrElse(num, 0) + 1))
        }
        
        var minlen = nums.length
        val degree = countmap.values.toList.max
        
        countmap.foreach { 
            case (k, v) => if (v == degree) minlen = Math.min(minlen, rightmap(k) - leftmap(k) + 1) 
        }
        
        minlen
    }
    

    '


  • 0

    in JavaScript, with only one map used:
    var findShortestSubArray = function(nums) {
    var m = new Map(),
    degree = 1,
    whichDegree = nums[0]
    for (var i = 0; i < nums.length; i++) {
    if (m.has(nums[i])) {
    var pos = m.get(nums[i])
    pos.push(i)
    if (pos.length > degree) {
    degree = pos.length
    whichDegree = nums[i]
    } else if (pos.length == degree && pos[pos.length - 1] - pos[0] < m.get(whichDegree)[m.get(whichDegree).length - 1] - m.get(whichDegree)[0]) {
    degree = pos.length
    whichDegree = nums[i]
    }
    } else m.set(nums[i], [i])
    }
    return m.get(whichDegree)[m.get(whichDegree).length - 1] - m.get(whichDegree)[0] + 1
    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.