숫자에 대해 무엇이 그렇게 특별 할 수 있습니까?
우리가 알아 보자.
우리는 N 개의 숫자 배열을 가지고 있습니다. 숫자 자체를 제외하고 하나 이상의 숫자로 나눌 수있는 숫자는 특별 할 수 있습니다.
먼저 다른 것으로 넘어 가기 전에 몇 가지 예를 통해이 문제를 해결하겠습니다.
1,2,3 배열
특수 번호 2 및 3
이유는 무엇입니까?
2도 1로 나눌 수 있습니다.
1,2,5,9의 배열
특수 번호는 2,5 및 9입니다.
이유는 무엇입니까?
이 숫자는 1로 나눌 수 있으므로
2,3,4,6,8,9의 배열
특수 번호는 4.6.8.9입니다.
둘째,이 문제에 접근하는 방법을 살펴 보겠습니다.
차례
특수 번호에 대한 접근 방식 1
브 루트 포스
- 우리는 배열을 통과합니다.
- 각 요소를 나누는 요소를 확인합니다.
특수 번호에 대한 Java 코드
// "static void main" must be defined in a public class.
public class Main
{
public static void diCheck(List<Integer> arr, int n)
{
Set<Integer> store = new HashSet<Integer>();
for(int i=0;i<arr.size();i++)
{
for(int j=i+1;j<arr.size();j++)
{
if(arr.get(j)%arr.get(i)==0)
store.add(arr.get(j));
}
}
for(Integer a:store)
{
System.out.print(a+" ");
}
}
public static void main(String[] args)
{
List<Integer> arr = Arrays.asList(1, 2, 3, 8, 6, 9, 5);
int n = arr.size();
diCheck(arr, n);
}
}
특수 번호에 대한 C ++ 코드
void diCheck(int arr[], int n)
{
unordered_set<int> store;
int maxs = -1;
for (int i = 0; i < n; i++)
{
for(int j=i+1;j<n;j++)
{
if(arr[j]%arr[i]==0)
store.insert(arr[j]);
}
}
for (auto x : store)
cout << x << " ";
}
int main()
{
int arr[] = { 1, 2, 3, 5, 8, 6, 9, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
diCheck(arr, n);
return 0;
}
복잡성 분석
시간 복잡도 = O (n ^ 2)
어떻게?
- 위의 접근 방식은 두 개의 루프를 사용합니다.
- 첫째, 제수를 넘어갈 바깥 쪽
- 둘째. 배당금을 넘을 내부 하나
- 이것은 시간 복잡도를 O (n ^ 2)로 가져옵니다.
공간 복잡성 = O (1)
어떻게?
변수 만 사용하므로 공간이 많이 필요하지 않습니다.
특수 번호에 대한 접근 방식 2
해시 테이블 사용
첫째, 우리는 접근 작은 입 크기의 입맛에 맞는 조각으로.
- 먼저 모든 요소를 정렬합니다.
- 변수를 사용하여 최대 요소 찾기
- 최대 요소가 필요하십니까?
- 해당 숫자까지 사용 가능한 제수를 찾는 데 사용하려면
- num * 2부터 시작합니다
- 배수를 얻기 위해 그 자체에 숫자를 더합니다.
- 멀티플을 얻을 때마다 세트에 저장합니다.
- 우리가 얻은 숫자가 중복되지 않도록 숫자를 집합에 저장합니다.
- 제수가 있으면 숫자는 특별합니다.
- 따라서 특수 번호가 추가됩니다.
둘째, 전체 프로세스를 실행할 작은 이미지를 얻습니다. 이렇게하면 문제를 파악할 수없는 모든 사람이 문제를 완전히 이해할 수 있습니다.
여기의 빨간색 부분은 번호가 이미지도에 추가되었음을 나타냅니다.
자바 코드
// "static void main" must be defined in a public class.
public class Main
{
public static void diCheck(List<Integer> arr, int n)
{
List<Integer> store = new ArrayList<Integer>();
int max = Integer.MIN_VALUE;
for (int i = 0; i < n; i++)
{
store.add(arr.get(i));
max = Math.max(max,arr.get(i));
}
LinkedHashSet<Integer>ans=new LinkedHashSet<Integer>();
for(int i=0;i<n;i++)
{
if(arr.get(i)!=0)
{
for(int j=arr.get(i)*2;j<max;j++)
{
if(store.contains(j))
ans.add(j);
}
}
}
List<Integer>ret=new ArrayList<Integer>(ans);
for(int i=0;i<ret.size();i++)
System.out.print(ret.get(i)+" ");
}
public static void main(String[] args)
{
List<Integer> arr = Arrays.asList(1, 2, 3, 8, 6, 9, 5);
int n = arr.size();
diCheck(arr, n);
}
}
C ++ 코드
void diCheck(int arr[], int n)
{
unordered_set<int> store;
int maxs = -1;
for (int i = 0; i < n; i++)
{
store.insert(arr[i]);
//Finding the max element
maxs= max(maxs, arr[i]);
}
// Traversing the array elements and storing the multiples
unordered_set<int> res;
for (int i = 0; i < n; i++)
{
if (arr[i] != 0)
{
for (int j = arr[i] * 2; j <= maxs; j++)
{
if (store.find(j) != store.end())
res.insert(j);
}
}
}
unordered_map<int, int> map;
for(int i = 0; i < n; i++)
map[arr[i]]=map[arr[i]]+1;
unordered_map<int, int>::iterator it;
vector<int> ans;
for (it = map.begin(); it != map.end(); it++)
{
if (it->second >= 2)
{
if (res.find(it->first) == res.end())
{
int val = it->second;
while (val--)
ans.push_back(it->first);
}
}
// If frequency is greater than 1 and is divisible by any other number
if (res.find(it->first) != res.end())
{
int val = it->second;
while (val--)
ans.push_back(it->first);
}
}
//Printing special numbers
for (auto x : ans)
cout << x << " ";
}
int main()
{
int arr[] = { 1, 2, 3, 5, 8, 6, 9, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
diCheck(arr, n);
return 0;
}
1, 2, 3, 5, 8, 6, 9, 10
2,3,5,8,9,10
참고 : 위의 접근 방식은 작은 숫자에만 적합합니다.
특수 번호에 대한 복잡성 분석
시간 복잡도 = O (n ^ 2)
- 접근 방식의 시간 복잡도는 O (n ^ 2)입니다.
- 정렬에는 O (n log n) 시간이 걸립니다.
- 외부 루프를 살펴보고 해시에서 숫자를 선택합니다.
- 내부 루프에서 제수를 찾아서 세트에 추가합니다.
- 결국 시간 복잡도를 O (nlogn) + O (n ^ 2)로 합산
- n ^ 2> n logn으로
- 시간 복잡도는 O (n ^ 2)가됩니다.
공간 복잡성 = O (n)
- 우리는 요소를 추적하기 위해 해시와 세트를 사용합니다.
- n 크기의 배열 / ArrayList / 벡터가 제공됩니다.
- 따라서 모든 요소를 저장하는 데 사용되는 공간의 합계는 O (n)입니다.
