Tuesday, January 17, 2017

368. Largest Divisible Subset

Q:
Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0.
If there are multiple solutions, return any subset is fine.
Example 1:
nums: [1,2,3]

Result: [1,2] (of course, [1,3] will also be ok)
Example 2:


nums: [1,2,4,8]

Result: [1,2,4,8]
A:



public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        List<Integer> res = new LinkedList<>();
        Map<Integer,Integer> map = new HashMap<>();
        for(int val : nums1)
            map.put(val, 1+ (map.containsKey(val)?map.get(val):0));
        for(int val : nums2){
            if(map.containsKey(val)){
                res.add(val);
                map.put(val,map.get(val)-1);
                if(map.get(val)==0)
                    map.remove(val);
            }
        }
        int A[] = new int[res.size()];
        for(int i = 0;i<res.size();i++)
            A[i] = res.get(i);
        
        return A;
    }
}
Mistakes:








No comments:

Post a Comment