Arrays & Hashing (1)

 

217. Contains Duplicate   : 같은 숫자가 존재하나 ?

import java.util.* ; 

class Solution {
    public boolean containsDuplicate(int[] nums) {    
        int size = Arrays.stream(nums).
                distinct().
                boxed().
                collect(Collectors.toList()).size();
        return size != nums.length;
    }
}

 -> HashSet 또는 map 을 사용하여 o(N )  으로 접근 하는 풀이도 가능 

 

 

242. Valid Anagram

 

주어진 문자열이 재구성 가능 한지 확인 하는 코드 , 두개의 문자를 비교하는것은 

Char arr 이후 arrays. 의 api 를  이용한 풀이를 생각하자 . 

import java.util.* ; 

class Solution {
    public boolean isAnagram(String s, String t) {

        if(s.length() != t.length()) return false;

        char[] sarr = s.toCharArray() ;
        char[] tarr = t.toCharArray() ;
        Arrays.sort(sarr);
        Arrays.sort(tarr);
        
        return Arrays.equals(sarr,tarr);
    }
}

 

1. Two Sum

 

정답 배열을 사전에 굳이 만들 필요 없이 결과를 제출 할때 생성을 하자. 

+ 문제 특성을 생각 하여 반환할 두개의  접근 index 를 잘 두자.

public int[] twoSum(int[] nums, int target) {
        if(nums.length == 2) {
            return new int[] {0,1}; 
        }
        Map<Integer,Integer> map = new HashMap<>();  /// save value and index

        for(int i =0 ; i < nums.length;i++){
            int check = target - nums[i];
            if(map.containsKey(check)){
                return new int[]{ map.get(check) , i } ;
            }else{
                map.put(nums[i],i);
            }
        }
        // case of Error
        return new int[2]; 
    }

 

49. Group Anagrams

 

1. Brutal

isAnagram 응용 , 함수를 일부분 만들어서 쓰자. 

String s = "A"  를 한줄로 double list 를 만들자. 

 public List<List<String>> groupAnagrams(String[] strs) {
        
        if(strs.length == 1) return Collections.singletonList(Collections.singletonList(strs[0]));
        
        List<List<String>> ans = new ArrayList<>();
        List<String> tmp = new ArrayList<>();
        tmp.add(strs[0]);
        ans.add(tmp);
        
        for(int i = 1 ; i  < strs.length;i++ ) {
            boolean find = false;
            tmp = new ArrayList<>();
            for(int j  = 0 ; j< ans.size();j++) {
                String check = ans.get(j).get(0);
                if(isAnagram(check,strs[i])){
                    ans.get(j).add(strs[i]);
                    find = true;
                    break;
                }
            }
            if(!find)
            {
                tmp.add(strs[i]);
                ans.add(tmp);
            }
        }
        return ans ;
    }

 

2. Map  이용, 

 

 

347. Top K Frequent Elements

 

Double List 에서 index 0 을 기준으로 오름 차순을 만드는 방법은 다음과 같다.

  

doubleList.sort((a,b) ->b.get(0) - a.get(0) );

public int[] topKFrequent(int[] nums, int k) {
        int[] re = new int[k];
        Map<Integer,Integer>  m = new HashMap<>();
        for(int item : nums) {
            m.put(item,m.getOrDefault(item,0)+1);
        }
        List<List<Integer>> ans = new ArrayList<>();
        for(Map.Entry<Integer,Integer> item :m.entrySet()) {
            List<Integer> list = Arrays.asList(item.getValue(),item.getKey());
            ans.add(list);
        }

        ans.sort((a,b) ->b.get(0) - a.get(0) );

        for(int i =0 ; i < k ;i++){
            re[i] = ans.get(i).get(1);
        }
        return re;
    }

 

깔끔한 Stream :

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.merge(num, 1, Integer::sum);
        }
        return map.entrySet()
                .stream()
                .sorted(Collections.reverseOrder(Map.Entry.comparingByValue()))
                .limit(k)
                .map(Map.Entry::getKey)
                .mapToInt(Integer::intValue)
                .toArray();
    }
}