정수 배열이 여러 개 있다고 가정 해 보겠습니다. 첫 번째 정수와 두 번째 정수의 차이가 1이되도록 정수 목록을 찾는 좋은 방법은 무엇입니까?첫 번째 숫자와 두 번째 숫자의 차이가 1이되도록 서로 다른 배열에 저장된 숫자 쌍을 찾는 좋은 방법은 무엇입니까?
필자는 당연히 서로 다른 번호를 찾거나 하나가 더 커질 때까지 서로의 목록을 살펴 보는 순진한 알고리즘을 작성할 수 있습니다. 보다 우아한 솔루션이 있습니까?
나는 계산을 빠르게하기 위해 그 지식에 대한 약간의 사용이있을 것이라고 추측하고 있기 때문에 차이가 1이라는 조건 만 언급합니다. 나는 '히트'조건이 다른 것이라면 알고리즘은 똑같이 작동 할 것이라고 상상한다.
일부 배경 : 나는 약간의 연구 수학에 종사하고 있으며 특정 구성의 예를 찾고 있습니다. 어떤 도움이라도 대단히 감사 할 것입니다.
최종 단계는 통일이 아니라 비교 인 클래식 merge sort의 좋은 후보자처럼 들립니다.
차이의 크기는 영향을 미치지 않지만 정보를 추가해 주셔서 감사합니다.
두 번째 목록이 배열에 있음에도 불구하고 일종의 해시 맵에 넣을 수 있다면 단순한 접근 방식보다 빨리 만들 수 있습니다.
기본적으로 첫 번째 배열을 반복합니다. 해시 맵에 현재 배열 값보다 큰 객체가 있는지 확인하십시오.
그런 식으로 요구 사항을 충족하는 숫자 쌍을 만들 수 있습니다.
내가 원하는대로 융통성있게 사용할 수 있을지 모르겠다.
기본적으로 더 나은 솔루션을 찾을 수 있도록 다른 데이터 구조를 고려할 수 있습니다.
각 배열을 정렬하여 시작할 것입니다. O (n log (n)) 시간에 실행되는 알고리즘을 사용하는 것이 바람직합니다.
정렬 된 배열이 여러 개있는 경우 각 배열의 시작 부분에 포인터를 설정하고 포인터의 값에서 +/- 1 차이를 확인하고 가장 작은 값의 값을 증가시킬 수 있습니다. 하나의 배열을 제외한 모든 배열의 최대 길이에 도달 할 때까지 반복합니다.
더 최적화하려면 포인터 값을 정렬 된 연결 목록에 유지하고 삽입 함수로 검사 함수를 작성하십시오. 각 증분에 대해 목록에서 이전 값을 제거하고 가능한 일치 항목보다 큰 용어를 얻을 때까지 +/- 1 비교 검사 목록을 단계별로 실행할 수 있습니다. 그렇게하면 bazillion 배열을 검색하는 경우 모든 bazillion 포인터 값을 검사 할 필요가 없습니다. 너무 큰 값을 찾을 때까지만 확인하고 큰 값은 모두 무시하면됩니다. (예 : 조건 또는 배열의 수의 범위 등) 배열에 대한 자세한 정보를 가지고있는 경우에
, 난 당신을 통해이 훨씬 빠른 알고리즘을 만들기 위해 그 활용 수있는 방법을 볼 수 있습니다 배열 속성을 영리하게 사용합니다.
당신은 정렬에서 o (n 로그 n) 있습니다.
일부 동적 쿼리 집합이있는 경우 각 요소에 대해 o (log n)에서 검색 할 수도 있습니다. 배열을 정렬 한 다음 첫 번째 배열의 각 요소에 대해 두 번째 배열의 upper_bound 및 lower_bound를 검색하여 차이를 확인할 수 있습니다.
배열이 정렬되어 있습니까? –