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
    };


  • 0
    P

    16 ms C Solution

    typedef struct hashmap{
    int freq;
    int loc[2];
    }hash_m;

    int findShortestSubArray(int* nums, int numsSize) {
    hash_m hash[50000]={0};
    int max=0,val;
    for(int i=0;i<numsSize;i++){
    if(hash[nums[i]].freq == 0){
    hash[nums[i]].loc[0]=i;
    hash[nums[i]].loc[1]=i;
    }
    else{
    hash[nums[i]].loc[1]=i;
    }
    hash[nums[i]].freq++;
    }

    for(int i=0;i<numsSize;i++){
        if(max < hash[nums[i]].freq){
            max = hash[nums[i]].freq;
            val = hash[nums[i]].loc[1] - hash[nums[i]].loc[0];
        }
        else if(max == hash[nums[i]].freq){
            if((hash[nums[i]].loc[1] - hash[nums[i]].loc[0]) < val)
                val = hash[nums[i]].loc[1] - hash[nums[i]].loc[0];
        }
    }
    
    
    return  val+1; 
    

    }


  • 0
    S

    class Solution:
    def findShortestSubArray(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    degree = 1
    item = nums[0]
    mydic={}
    indexend = 0
    if len(nums) == 1:
    return 1
    for i in range(0,len(nums)):
    if nums[i] in mydic:
    mydic[nums[i]][0] = mydic[nums[i]][0] + 1
    if mydic[nums[i]][0] > degree:
    degree = mydic[nums[i]][0]
    item = nums[i]
    indexend = i
    elif mydic[nums[i]][0] == degree:
    if (i-mydic[nums[i]][1]+1) <(indexend-mydic[item][1]+1):
    item = nums[i]
    indexend = i
    else:
    mydic[nums[i]]=[1,i]

        return (indexend - mydic[item][1])+1

  • 0
    R

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

        Map<Integer, NumInfo> map = new HashMap<>();
        for (int i=0; i<nums.length; i++) {
            NumInfo info = map.getOrDefault(nums[i], new NumInfo(nums[i]));
            if (info.first == -1) {
                info.first = i;
            }
            info.last = i;
            info.count++;
            map.put(nums[i], info);
        }
        
        PriorityQueue<NumInfo> queue = new PriorityQueue<>(new Comparator<NumInfo>() { 
            
            @Override
            public int compare(NumInfo o1, NumInfo o2) {
                if (o1.count > o2.count)
                    return -1;
                
                if (o1.count < o2.count)
                    return 1;
                
                if (o1.last-o1.first < o2.last-o2.first)
                    return -1;
                else
                    return 1;
            }
        });
        
        for (int n : map.keySet()) {
            queue.add(map.get(n));
        }
        
       NumInfo obj = queue.poll();
        return obj.last-obj.first+1;
    }
    
    private class NumInfo {
        int num ;
        
        public NumInfo(int num) {
            this.num = num;
        }
        int first = -1;
        int last = -1;
        int count = 0;
    }
    

    }


  • 0
    E

    Here is a one pass solution (only scans the array once and no need to scan the map again)
    in the map keep the current count of the Integer and the position once it was first seen, when see a new int during the scan, fetch the record of the current Int, and add the occurrence , if the occurrence is lesser than the global max, do nothing. If the occurrence equals to the global max, update the len if needed with the current numbers' current seen - first seen position +1. If the occurrence is larger than the global max, replace the global max with the local max and update the len with the current len reading. (Beat 80% Java)

    public int findShortestSubArray(int[] nums) {
    Map<Integer,Integer[]> lookup = new HashMap<>();
    int degree = 0 ;
    int len = Integer.MAX_VALUE;
    for (int idx = 0 ; idx < nums.length; idx ++) {
    Integer[] res = lookup.get(nums[idx]);
    if (res == null) {
    res = new Integer[] {1, idx} ;
    }
    res[0] ++;
    if (res[0] >=degree) {
    if (res[0] > degree) {
    degree = res[0];
    len = idx - res[1] +1;
    } else {
    len = Math.min(len, idx-res[1] +1);
    }
    }

            lookup.put(nums[idx], res); 
        
        }
        return len;
    }

  • 0
    S

    #ruby #codegolf

    Short Version:

    a.each.with_object({}).with_index{|(i,h),x|h[i]=(h[i]||[])<<x}.values.map{|a|[a.size,a[-1]-a[0]]}.sort{|a,b|[a[0],b[-1]]<=>[b[0],a[-1]]}[-1][-1]+1
    

    Readable Version:

      h = Hash.new { |h,k| h[k] = [] }
      array.each.with_object(h)
           .with_index { |(i, h), idx| h[i] << idx }
           .values.map { |a| [a.size, a.last - a.first] }
           .sort       { |a, b| [a.first, b.last] <=> [b.first, a.last] }
           .last.last + 1
    

Log in to reply
 

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