0에서 n-1까지의 그룹 무게 판정
public static void main(String[] args) {
int[] data = {2, 3, 1, 0, 2, 5};
Main main = new Main();
main.isDuplicate(data);
}
public void isDuplicate(int[] arg){
HashSet set = new HashSet<>();
for (int a: arg) {
if (set.contains(a)) {
System.out.println(a);
} else {
set.add(a);
}
}
}
먼저 우리가 생각한 것은hash이다.hash를 통해 한 숫자가 이전에 O(1)만 있으면 되는 시간의 복잡도를 판단한다.hashset의 밑바닥이 바로hashmap의 키,즉hash의 실현이라는 것을 알 수 있다.
그러나 데이터가 매우 어지러울 때hash는 공간의 복잡도를 매우 소모한다.예를 들어 수열 01963, 2, 15는 동시에hash의 충돌 시간이 발생할 수 있다.
숫자이기 때문에 그 수열에 있는 숫자는 0-n-1에만 나타나기 때문에 우리는 직접 주소 지정법을 사용해서hash의 충돌 시간을 피할 수 있고 공간의 복잡도를 줄일 수 있다.
public static void main(String[] args) {
int[] data = {2, 3, 1, 0, 2, 5};
Main main = new Main();
main.isDuplicate(data);
}
public void isDuplicate(int[] data){
int len = data.length;
int[] array = new int[len+1];
for (int i = 0;i < len;i++){
if(array[data[i]+1]==0) {
array[data[i]+1] = data[i]+1;
}else if(array[data[i]+1]==data[i]+1){
System.out.println(data[i]);
}
}
}
그러나 이렇게 공간의 복잡도도 O(n)이라고 해도 O(1)의 복잡도, 즉 로컬로 비교하려면 어떻게 해야 합니까?
빠른 배열의 교환 사상을 로컬에서 사용하여 데이터의 위치를 신속하게 포지셔닝할 수 있다. 또한 우리는nums[i]==i, 현재 위치의 데이터는 현재 위치의 좌표와 같아야 한다고 규정한다.이렇게 하면 O(1)의 공간 책임도를 사용하여 위치를 다시 정할 수 있다.
public static void main(String[] args) {
int[] data = {2, 3, 1, 0, 2, 5};
Main main = new Main();
int[] duplication = new int[6] ;
main.isDuplicate(data,6,duplication);
System.out.println(duplication[0]);
}
public boolean isDuplicate(int[] data,int length,int[] duplication) {
if (data == null || length <= 0)
return false;
for(int i = 0; i < length; i++){
while(data[i]!=i){
if(data[i]==data[data[i]]){
duplication[0] = data[i];
return true;
}
swap(data,i,data[i]);
}
}
return false;
}
private void swap(int[] data, int i, int j) {
int a = data[i];
data[i] = data[j];
data[j] = a;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.