시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
차례
문제 정책
정수 숫자 배열이 주어지면 값의 빈도에 따라 오름차순으로 배열을 정렬합니다. 여러 값의 빈도가 동일한 경우 내림차순으로 정렬합니다.
예
nums = [1,1,2,2,2,3]
[3,1,1,2,2,2]
설명 :
'3'은 주파수 1, '1'은 주파수 2, '2'는 주파수 3입니다.
nums = [2,3,1,3,2]
[1,3,3,2,2]
설명 :
'2'와 '3'은 모두 빈도가 2이므로 내림차순으로 정렬됩니다.
접근
이 문제에서는 먼저 각 요소의 빈도를 세어야합니다. 이를 위해 우리는 해시 맵 Java에서 또는 C ++에서 정렬되지 않은 세트. 이제 결과 배열에 빈도가 높은 요소를 먼저 포함하려고합니다.
이를 위해 이미지도에 저장 한 총 주파수를 기준으로 주어진 입력 배열을 정렬 할 수 있습니다.
이제 함수 밖에서 비교기를 만들어야합니다. 여기서 우리는 두 요소 (a와 b)를 비교하고 각 요소의 빈도를 알고 있습니다. 따라서 a의 주파수가 b보다 크면 배열에서 a 앞에 b를 넣으십시오. 다음 경우는 a와 b의 주파수가 같으면 더 높은 값을 가진 요소를 먼저 배치하는 것입니다. 예:
사례
사례
암호알고리즘
- 해시 맵을 만듭니다.
- 루프를 실행하고 각 요소에 대해 맵에서 해당 요소의 개수를 1 씩 증가시킵니다.
- 이제 맵에 저장된 개수를 사용하여 두 정수를 비교하는 비교 함수를 만듭니다. 두 요소를 비교하고 위에서 설명한대로 순서를 결정합니다.
- 이 비교기를 사용하여 주어진 배열을 정렬합니다.
- 정렬 된 배열을 반환합니다.
실시
주파수를 증가시켜 배열 정렬을위한 C ++ 프로그램 Leetcode 솔루션
#include <bits/stdc++.h> using namespace std; bool comp(pair<int,int> p1,pair<int,int> p2) { if(p1.second == p2.second) return p1.first > p2.first; return p1.second < p2.second; } vector<int> frequencySort(vector<int>& nums) { unordered_map<int,int> m; for(auto x:nums) m[x]++; vector<pair<int,int> > v; for(auto p:m) v.push_back(p); sort(v.begin(),v.end(), comp); vector<int> res; for(auto p:v) { while(p.second--) res.push_back(p.first); } return res; } int main() { vector<int> nums = {2,3,1,3,2}; for(int x: frequencySort (nums)) cout<<x<<" "; return 0; }
1 3 3 2 2
주파수를 증가시켜 배열 정렬을위한 자바 프로그램 Leetcode 솔루션
import java.util.*; import java.lang.*; class Comp implements Comparator<Integer>{ Map<Integer,Integer>map=Rextester.map; public int compare(Integer a,Integer b){ if(map.get(a)>map.get(b))return 1; else if(map.get(b)>map.get(a))return -1; else{ if(a>b)return -1; else if(a<b)return 1; return 0; } } } class Rextester { static Map<Integer,Integer>map; public static int[] frequencySort(int[] nums) { map=new HashMap<Integer,Integer>(); for(int i:nums){ if(map.containsKey(i)){ map.put(i,1+map.get(i)); }else{ map.put(i,1); } } Integer[]arr=new Integer[nums.length]; int k=0; for(int i:nums){ arr[k++]=i; } Arrays.sort(arr,new Comp()); k=0; for(int i:arr){ nums[k++]=i; } return nums; } public static void main(String args[]) { int[]nums={1,1,2,2,2,3}; nums=frequencySort(nums); for(int i:nums) { System.out.print(i+" "); } } }
1 3 3 2 2
주파수 Leetcode 솔루션을 증가시켜 정렬 배열의 복잡성 분석
시간 복잡성
O (nlog (n)) : 여기서 n은 입력 배열의 크기입니다. 해시 맵의 삽입 및 액세스에는 n 개의 요소에 대해 O (n) 시간이 걸리고 정렬에는 nlogn 시간이 걸립니다. 따라서 시간 복잡도는 nlogn입니다.
공간 복잡성
의 위에) : 최악의 경우 배열에서 n 개의 다른 요소가 될 수 있습니다. 따라서 맵의 크기는 O (n)이됩니다.
