숫자 배열에서 누락 된 숫자를 찾는 가장 빠른 방법
1에서 100까지의 숫자 배열이 있습니다. (둘 다 포함). 배열의 크기는 100입니다. 숫자는 배열에 무작위로 추가 배열에는 임의의 빈 배열이 있습니다. 단어와 이름에 넣어야하는 번호를 찾는 가장 빠른 것은 무엇입니까? Java 솔루션이 최선을 다합니다.
O (n)에서받을 수 있습니다. 배열을 반복하고 모든 숫자의 합을 계산합니다. 이제 1에서 N까지의 자연수의 합은 Nx(N+1)/2. 귀하의 경우 N = 100.
에서 배열의 합을 혹니다 Nx(N+1)/2. 여기서 N = 100입니다.
그것은 누락 된 숫자입니다. 음성이 감지 될 수 있습니다.
// will be the sum of the numbers in the array.
int sum = 0;
int idx = -1;
for (int i = 0; i < arr.length; i++)
{
if (arr[i] == 0)
{
idx = i;
}
else
{
sum += arr[i];
}
}
// the total sum of numbers between 1 and arr.length.
int total = (arr.length + 1) * arr.length / 2;
System.out.println("missing number is: " + (total - sum) + " at index " + idx);
프로그래밍 언어에서 주어진 입력이 크면 오버플로되어 오답을 줄 수 있기 때문에 합산보다 안전한 XOR 연산을 사용할 수 있습니다.
솔루션으로 이동하기 전에 A xor A = 0. 따라서 두 개의 동일한 숫자를 XOR하면 값은 0입니다.
이제 배열에있는 요소를 XORing [1..n]하면 동일한 숫자가 취소됩니다. 그래서 결국 우리는 누락 된 번호를 얻을 것입니다.
// Assuming that the array contains 99 distinct integers between 1..99
// and empty slot value is zero
int XOR = 0;
for(int i=0; i<100; i++) {
if (ARRAY[i] != 0) // remove this condition keeping the body if no zero slot
XOR ^= ARRAY[i];
XOR ^= (i + 1);
}
return XOR;
//return XOR ^ ARRAY.length + 1; if your array doesn't have empty zero slot.
주어진 배열을 길이가 N 인 A라고 가정합니다. 주어진 배열에서 단일 배열이 0으로 채워져 가정합니다.
.NET에서 사용되는 알고리즘을 포함하는 모든 방법을 사용하여 문제에 대한 해결책을 사용할 수 있습니다 Counting sort. 그러나 사용 시간 및 공간 사용에서 두 가지 알고리즘이 있습니다. 하나는 주로 합산, 빼기 및 곱셈을 사용합니다. 다른 하나는 XOR을 사용합니다. 수학적으로 두 방법 모두 잘 작동합니다. 그러나 프로그래밍 방식으로 우리는 다음과 같은 주요 측정으로 모든 알고리즘을 평가해야합니다.
- 제한 사항 (입력 값이 큼 (
A[1...N]) 및 / 또는 입력 값 수가 큼 (N)) - 관련된 조건 검사 수
- 관련된 수학적 연산의 수와 유형
시간 및 / 또는 하드웨어 (하드웨어 자원 제한) 및 / 또는 소프트웨어 (운영 제한, 프로그래밍 언어 제한 등) 존재 제한이 있기 때문입니다. 각각의 장단점을 평가하고 평가할 수 있습니다. .
알고리즘 1 :
알고리즘 1에는 3 가지 구현이 있습니다.
수학 공식 (
1+2+3+...+N=(N(N+1))/2) 을하여 모든 숫자 (알 수없는 누락 된 숫자 포함)의 총합을 계산합니다 . 여기,N=100. 주어진 모든 숫자의 총합을 계산합니다. 첫 번째 결과에서 두 번째 결과를 빼면 누락 된 숫자가 제공됩니다.Missing Number = (N(N+1))/2) - (A[1]+A[2]+...+A[100])수학 공식 (
1+2+3+...+N=(N(N+1))/2) 을하여 모든 숫자 (알 수없는 누락 된 숫자 포함)의 총합을 계산합니다 . 여기,N=100. 그 결과에서 주어진 각 숫자를 빼면 누락 된 숫자가 제공됩니다.Missing Number = (N(N+1))/2)-A[1]-A[2]-...-A[100](
Note:두 번째 구현의 공식이 첫 번째에서 파생되었지만 수학적 관점에서 둘 다 동일합니다. 그러나 프로그래밍 관점에서 둘 다 다릅니다. 첫 번째 공식이 두 번째 공식보다 비트 오버플로가 더 많기 때문입니다. 덧셈이 뺄셈보다 빠르지 만 두 번째 구현은 큰 값을 더하여 발생하는 비트 오버플로 가능성을 줄입니다 (N+1수식에 ( )가 있기 때문에 여전히 매우 작은 기회가 있기 때문에 완전히 제거되지는 않습니다 ). 그러나 둘 다 곱셈으로 인해 비트 오버플로가 발생하는 경향이 똑같습니다. 한계는 두 구현 모두N(N+1)<=MAXIMUM_NUMBER_VALUE. 일 경우에만 올바른 결과를 제공한다는 것 입니다. 첫 번째 구현의 경우 추가 제한은Sum of all given numbers<=MAXIMUM_NUMBER_VALUE.) 인 경우에만 올바른 결과를 제공한다는 것 입니다.)모든 숫자의 총합 (알 수없는 누락 된 숫자 포함)을 계산하고 동일한 루프에서 주어진 각 숫자를 전달로합니다. 이것은 곱셈에 의한 비트 오버 플로우의 위험을 제거하지만 덧셈과 뺄셈에 의한 비트 오버 플로우의 경향이 있습니다.
//ALGORITHM missingNumber = 0; foreach(index from 1 to N) { missingNumber = missingNumber + index; //Since, the empty slot is filled with 0, //this extra condition which is executed for N times is not required. //But for the sake of understanding of algorithm purpose lets put it. if (inputArray[index] != 0) missingNumber = missingNumber - inputArray[index]; }
언어 (예 : C, C ++, Java 등)에서 정수 데이터 유형을 프로그래밍 비트 수가 제한 될 경우 위의 모든 구현이 합산, 빼기 및 곱셈으로 인해 발생하는 오버플로가 발생하여 잘못된 결과가 발생하기 때문에 발생합니다. 입력 값이 큰 경우 ( A[1...N]) 및 / 또는 입력 값이 많은 경우 ( N).
알고리즘 2 :
XOR의 속성을 사용하여 비트 오버플로 문제에 대해 걱정하지 않고 문제에 대한 해결책을 사용할 수 있습니다. 또한 XOR은 합산보다 안전하고 빠 사용합니다. 두 개의 동일한 숫자의 XOR이 0 ( A XOR A = 0) 과 같다는 XOR의 속성을 알고 있습니다. 1에서 N까지의 모든 숫자의 XOR (알 수없는 누락 된 숫자 포함)을 계산 한 다음 그 결과로 주어진 모든 숫자를 XOR하면 공통가 취소되고 (이후 A XOR A=0) 결국 누락 된 값을 얻습니다. 번호. 비트 오버플로 문제가 제거 및 XOR 기반 알고리즘을 모두 사용하여 솔루션을 얻을 수 있습니다. 그러나 XOR을 사용하는 알고리즘은 합산, 빼기 및 곱셈을 사용하는 알고리즘보다 안전하고 빠 사용합니다. 그리고 우리는 더하기, 빼기, 곱하기로 인한 추가적인 걱정을 피할 수 있습니다.
알고리즘 1의 모든 구현에서 더하기와 빼기 대신 XOR을 사용할 수 있습니다.
가정하자, XOR(1...N) = XOR of all numbers from 1 to N
구현 1 => Missing Number = XOR(1...N) XOR (A[1] XOR A[2] XOR...XOR A[100])
구현 2 => Missing Number = XOR(1...N) XOR A[1] XOR A[2] XOR...XOR A[100]
구현 3 =>
//ALGORITHM
missingNumber = 0;
foreach(index from 1 to N)
{
missingNumber = missingNumber XOR index;
//Since, the empty slot is filled with 0,
//this extra condition which is executed for N times is not required.
//But for the sake of understanding of algorithm purpose lets put it.
if (inputArray[index] != 0)
missingNumber = missingNumber XOR inputArray[index];
}
알고리즘 2의 세 가지 구현 모두 잘 작동합니다. 한 가지 최적화는 다음과 유사합니다.
1+2+....+N = (N(N+1))/2
우리는
1 XOR 2 XOR .... XOR N = {N if REMAINDER(N/4)=0, 1 if REMAINDER(N/4)=1, N+1 if REMAINDER(N/4)=2, 0 if REMAINDER(N/4)=3}
이를 수학적 귀납법으로 증명할 수 있습니다. 따라서 1에서 N까지의 모든 숫자를 XOR하여 XOR (1 ... N)의 값을 계산하는 대신이 공식을 사용하여 XOR 연산 수를 사용할 수 있습니다.
또한 위의 공식을 사용하여 XOR (1 ... N)을 계산하면 두 가지 구현이 있습니다. 현명한 구현, 계산
// Thanks to https://a3nm.net/blog/xor.html for this implementation
xor = (n>>1)&1 ^ (((n&1)>0)?1:n)
계산보다 빠르다
xor = (n % 4 == 0) ? n : (n % 4 == 1) ? 1 : (n % 4 == 2) ? n + 1 : 0;
따라서 최적화 된 Java 코드는 다음과 유연합니다.
long n = 100;
long a[] = new long[n];
//XOR of all numbers from 1 to n
// n%4 == 0 ---> n
// n%4 == 1 ---> 1
// n%4 == 2 ---> n + 1
// n%4 == 3 ---> 0
//Slower way of implementing the formula
// long xor = (n % 4 == 0) ? n : (n % 4 == 1) ? 1 : (n % 4 == 2) ? n + 1 : 0;
//Faster way of implementing the formula
// long xor = (n>>1)&1 ^ (((n&1)>0)?1:n);
long xor = (n>>1)&1 ^ (((n&1)>0)?1:n);
for (long i = 0; i < n; i++)
{
xor = xor ^ a[i];
}
//Missing number
System.out.println(xor);
이것은 아마존 인터뷰 질문이 원래 여기에 답변되었습니다. 51 개의 숫자 배열에 1에서 52까지의 숫자 가 있습니다. 어떤 숫자가 누락되었는지 알아내는 가장 좋은 방법은 무엇입니까?
다음과 같이 대답했습니다.
1) Calculate the sum of all numbers stored in the array of size 51.
2) Subtract the sum from (52 * 53)/2 ---- Formula : n * (n + 1) / 2.
그것은 또한 여기에 블로그 : 소프트웨어 직업-인터뷰 질문
다음은 정수 배열에서 누락 된 숫자를 찾는 간단한 프로그램입니다.
ArrayList<Integer> arr = new ArrayList<Integer>();
int a[] = { 1,3,4,5,6,7,10 };
int j = a[0];
for (int i=0;i<a.length;i++)
{
if (j==a[i])
{
j++;
continue;
}
else
{
arr.add(j);
i--;
j++;
}
}
System.out.println("missing numbers are ");
for(int r : arr)
{
System.out.println(" " + r);
}
5050- (배열에있는 모든 값의 합계) = 누락 된 숫자
int sum = 0;
int idx = -1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0) idx = i; else sum += arr[i];
}
System.out.println("missing number is: " + (5050 - sum) + " at index " + idx);
배열이 이미 정렬 된 검색하지 않고 하나의 숫자 만 누락 된 경우 이진을 사용하여 로그 (n) 시간에서 누락 된 숫자를 사용할 수 있습니다.
public static int getMissingInt(int[] intArray, int left, int right) {
if (right == left + 1) return intArray[right] - 1;
int pivot = left + (right - left) / 2;
if (intArray[pivot] == intArray[left] + (intArray[right] - intArray[left]) / 2 - (right - left) % 2)
return getMissingInt(intArray, pivot, right);
else
return getMissingInt(intArray, left, pivot);
}
public static void main(String args[]) {
int[] array = new int[]{3, 4, 5, 6, 7, 8, 10};
int missingInt = getMissingInt(array, 0, array.length-1);
System.out.println(missingInt); //it prints 9
}
최근에 나는 면접에서 (정확히 똑같은) 질문이 없었고, 인터뷰에서 똑같은 질문을받은 친구로부터도 들었습니다. 여기에 OP 질문에 대한 대답과 대답으로 질문 할 수있는 몇 가지 변형이 있습니다. 답변 예는 Java 로 제공 됩니다.
Java 솔루션이 최선을 다합니다.
변형 1 :
1부터 100까지의 숫자 배열 (둘 다 포함) ... 숫자가 배열에 무작위로 추가 배열에 임의의 빈 배열이 하나 있습니다.
public static int findMissing1(int [] arr){
int sum = 0;
for(int n : arr){
sum += n;
}
return (100*(100+1)/2) - sum;
}
설명 : 이 솔루션은 (다른 많은 솔루션은 여기에 게시 된)의 공식을 기반으로 우리에게 1에서 모든 자연수의 합을 제공합니다 (이 사건에서 100). 이제 1에서 100까지의 숫자를 사용하여 배열에서 기존의 숫자를 사용합니다.Triangular numbernn
변형 2 :
1에서 n까지의 숫자 배열 (최대 숫자를 알 수 없음)
public static int findMissing2(int [] arr){
int sum = 0, max = 0;
for(int n : arr){
sum += n;
if(n > max) max = n;
}
return (max*(max+1)/2) - sum;
}
설명 : 이 솔루션에서는 최대 수가 주어지지 사고 기 때문에 찾아야합니다. 최대 수를 많은 후-논리는 동일합니다.
변형 3 :
1에서 n까지의 숫자 배열 (최대 개수는 알 수 없음), 배열에 두 개의 임의의 빈 배열이 있습니다.
public static int [] findMissing3(int [] arr){
int sum = 0, max = 0, misSum;
int [] misNums = {};//empty by default
for(int n : arr){
sum += n;
if(n > max) max = n;
}
misSum = (max*(max+1)/2) - sum;//Sum of two missing numbers
for(int n = Math.min(misSum, max-1); n > 1; n--){
if(!contains(n, arr)){
misNums = new int[]{n, misSum-n};
break;
}
}
return misNums;
}
private static boolean contains(int num, int [] arr){
for(int n : arr){
if(n == num)return true;
}
return false;
}
설명 : 이 솔루션에서는 최대 숫자가 제공되지 않지만 (이전에서와 같이) 하나가 아닌 두 개의 숫자가 누락 될 수도 있습니다. 따라서 처음에는 이전과 동일한 논리로 누락 된 숫자의 합을 찾습니다. 두 번째는 누락 된 사라와 마지막 (아마도) 누락 된 숫자 사이에서 더 작은 숫자를 찾아 불필요한 검색을 줄입니다. 셋째, Javas Array (컬렉션이 아님)에는 indexOf또는로 메서드가 없기 때문에 contains논리에 작은 공동 가능한 메서드를 추가했습니다. 넷째, 첫 번째 누락 된 숫자가 발견되면 두 번째는 누락 된 것에서 빼는 것입니다. 하나의 숫자 만 누락 된 경우 배열의 두 번째 숫자는 0이됩니다.
변형 4 :
1에서 n까지의 숫자 배열 (최대 숫자는 알 수 없음), X 누락 (누락 된 숫자의 양은 알 수 없음)
public static ArrayList<Integer> findMissing4(ArrayList<Integer> arr){
int max = 0;
ArrayList<Integer> misNums = new ArrayList();
int [] neededNums;
for(int n : arr){
if(n > max) max = n;
}
neededNums = new int[max];//zero for any needed num
for(int n : arr){//iterate again
neededNums[n == max ? 0 : n]++;//add one - used as index in second array (convert max to zero)
}
for(int i=neededNums.length-1; i>0; i--){
if(neededNums[i] < 1)misNums.add(i);//if value is zero, than index is a missing number
}
return misNums;
}
설명 : 이 솔루션에서는 이전과 많은 경우에 최대 수를 알 수 없습니다 둘 이상의 숫자가 누락 될 수 없습니다 변형이 변형에서는 몇 개인 지 알 수 없습니다. 논리의 시작은 동일합니다-최대 수를 찾으십시오. 그런 다음 0으로 배열을 초기화합니다.이 배열 다른 것은 초기화합니다 index. 그 값은 1 씩 증가합니다 (최대 값은 0으로 변환 됨).
노트
다른 언어로 된 예제 나이 질문의 다른 흥미로운 변형을 원하신다면, 제 저장소Github 에서 인터뷰 질문 및 답변 을 확인하실 수 있습니다 .
글쎄, 블룸 필터를 사용하십시오.
int findmissing(int arr[], int n)
{
long bloom=0;
int i;
for(i=0; i<;n; i++)bloom+=1>>arr[i];
for(i=1; i<=n, (bloom<<i & 1); i++);
return i;
}
이것은 매우 가깝습니다.
int sumNumbers = 0;
int emptySlotIndex = -1;
for (int i = 0; i < arr.length; i++)
{
if (arr[i] == 0)
emptySlotIndex = i;
sumNumbers += arr[i];
}
int missingNumber = 5050 - sumNumbers;
예를 들어, 반복적 인 추가를 포함하지 않고 n (n + 1) / 2 공식이 인터뷰 시간에 도달하지 않는 솔루션입니다.
4 개의 int (32 비트) 또는 2 개의 int (64 비트) 배열을 유지합니다. 마지막 int를 (-1 & ~ (1 << 31)) >> 3으로 초기화합니다. (100보다 큰 비트는 1로 설정 됨) 또는 루프를 사용하여 100보다 큰 비트를 수 있습니다.
- (예 : 71은 오른쪽에서 오른쪽으로 7 번째 비트의 3 번째 정수에 설정됩니다).
- 4 개의 int (32 비트 버전) 또는 2 개의 int (64 비트 버전)의 배열을 봅니다.
public int MissingNumber(int a[])
{
int bits = sizeof(int) * 8;
int i = 0;
int no = 0;
while(a[i] == -1)//this means a[i]'s bits are all set to 1, the numbers is not inside this 32 numbers section
{
no += bits;
i++;
}
return no + bits - Math.Log(~a[i], 2);//apply NOT (~) operator to a[i] to invert all bits, and get a number with only one bit set (2 at the power of something)
}
예 : (32 비트 버전)에서는 누락 된 숫자가 58이라고 가정합니다. 이는 두 번째 정수의 26 번째 비트 (왼쪽에서 오른쪽)가 0으로 설정합니다.
첫 번째 int는 -1 (모든 비트가 설정 됨) 두 번째 정수에 대해 계속해서 숫자 32를 "no"에 더합니다. 두 번째 int는 -1 (비트가 설정되지 않음) NOT (~) 연산자는 64를 얻는 숫자입니다. 가능한 숫자는 x의 거듭 제곱에서 2이고 우리는 밑수 2의 로그를 사용하여 x를 계산할 수 있습니다. 이 경우 log2 (64) = 6 => 32 + 32-6 = 58이됩니다.
도움이 되셨기를 바랍니다.
가장 많이 사용되는 솔루션은 모든 항목을 반복하고 bitset을 사용하여 하나의 숫자를 기억 한 다음 0 비트를 테스트하는 것입니다. 0 비트 항목은 누락 된 숫자입니다.
이것은 검색 문제가 아닙니다. 당신이 체크섬을 알고 있는지 궁금합니다. 바이너리 또는 for 루프 또는 여러 개의 고유 한 고유 한 정수를 보유하고있는 임의의 정수 질문은 "하나의 빈 비용"을 규정합니다. 이 경우 스트림을 사용할 수 있습니다. "숫자가 배열에 무작위로 추가됩니다"라는 조건은 더없이 의미가 없습니다. 질문은 배열이 정수 1로 시작해야 할 가정하지 시작합니다.
int[] test = {2,3,4,5,6,7,8,9,10, 12,13,14 };
/*get the missing integer*/
int max = test[test.length - 1];
int min = test[0];
int sum = Arrays.stream(test).sum();
int actual = (((max*(max+1))/2)-min+1);
//Find:
//the missing value
System.out.println(actual - sum);
//the slot
System.out.println(actual - sum - min);
성공 시간 : 0.18 메모리 : 320576 신호 : 0
여기 에서이 아름다운 해결책을 찾았습니다.
http://javaconceptoftheday.com/java-puzzle-interview-program-find-missing-number-in-an-array/
public class MissingNumberInArray
{
//Method to calculate sum of 'n' numbers
static int sumOfNnumbers(int n)
{
int sum = (n * (n+1))/ 2;
return sum;
}
//Method to calculate sum of all elements of array
static int sumOfElements(int[] array)
{
int sum = 0;
for (int i = 0; i < array.length; i++)
{
sum = sum + array[i];
}
return sum;
}
public static void main(String[] args)
{
int n = 8;
int[] a = {1, 4, 5, 3, 7, 8, 6};
//Step 1
int sumOfNnumbers = sumOfNnumbers(n);
//Step 2
int sumOfElements = sumOfElements(a);
//Step 3
int missingNumber = sumOfNnumbers - sumOfElements;
System.out.println("Missing Number is = "+missingNumber);
}
}
function solution($A) {
// code in PHP5.5
$n=count($A);
for($i=1;$i<=$n;$i++) {
if(!in_array($i,$A)) {
return (int)$i;
}
}
}
공작의 숫자에서 누락 된 숫자 찾기. 기억해야 할 IMP 포인트.
- 배열을 정렬해야합니다 ..
- 함수는 여러 누락에 대해 작동하지 않습니다.
시퀀스는 AP 집합니다.
public int execute2(int[] array) { int diff = Math.min(array[1]-array[0], array[2]-array[1]); int min = 0, max = arr.length-1; boolean missingNum = true; while(min<max) { int mid = (min + max) >>> 1; int leftDiff = array[mid] - array[min]; if(leftDiff > diff * (mid - min)) { if(mid-min == 1) return (array[mid] + array[min])/2; max = mid; missingNum = false; continue; } int rightDiff = array[max] - array[mid]; if(rightDiff > diff * (max - mid)) { if(max-mid == 1) return (array[max] + array[mid])/2; min = mid; missingNum = false; continue; } if(missingNum) break; } return -1; }
이 프로그램은 누락 된 번호를 찾습니다
<?php
$arr_num=array("1","2","3","5","6");
$n=count($arr_num);
for($i=1;$i<=$n;$i++)
{
if(!in_array($i,$arr_num))
{
array_push($arr_num,$i);print_r($arr_num);exit;
}
}
?>
예를 들어 빠른 정렬을 사용하여 숫자를 정렬 할 수 있습니다. 그런 다음 for 루프를 사용하여 1부터 100까지 정렬 된 배열을 반복합니다. 각 반복에서 배열의 숫자를 루프 증분과 비교합니다. 강화 증분이 배열 값과 같지 않다면 누락 된 번호와 누락 된 색인을 찾았습니다.
다음은 주어진 배열에서 누락 된 모든 숫자를 찾는 솔루션입니다.
public class FindMissingNumbers {
/**
* The function prints all the missing numbers from "n" consecutive numbers.
* The number of missing numbers is not given and all the numbers in the
* given array are assumed to be unique.
*
* A similar approach can be used to find all no-unique/ unique numbers from
* the given array
*
* @param n
* total count of numbers in the sequence
* @param numbers
* is an unsorted array of all the numbers from 1 - n with some
* numbers missing.
*
*/
public static void findMissingNumbers(int n, int[] numbers) {
if (n < 1) {
return;
}
byte[] bytes = new byte[n / 8];
int countOfMissingNumbers = n - numbers.length;
if (countOfMissingNumbers == 0) {
return;
}
for (int currentNumber : numbers) {
int byteIndex = (currentNumber - 1) / 8;
int bit = (currentNumber - byteIndex * 8) - 1;
// Update the "bit" in bytes[byteIndex]
int mask = 1 << bit;
bytes[byteIndex] |= mask;
}
for (int index = 0; index < bytes.length - 2; index++) {
if (bytes[index] != -128) {
for (int i = 0; i < 8; i++) {
if ((bytes[index] >> i & 1) == 0) {
System.out.println("Missing number: " + ((index * 8) + i + 1));
}
}
}
}
// Last byte
int loopTill = n % 8 == 0 ? 8 : n % 8;
for (int index = 0; index < loopTill; index++) {
if ((bytes[bytes.length - 1] >> index & 1) == 0) {
System.out.println("Missing number: " + (((bytes.length - 1) * 8) + index + 1));
}
}
}
public static void main(String[] args) {
List<Integer> arrayList = new ArrayList<Integer>();
int n = 128;
int m = 5;
for (int i = 1; i <= n; i++) {
arrayList.add(i);
}
Collections.shuffle(arrayList);
for (int i = 1; i <= 5; i++) {
System.out.println("Removing:" + arrayList.remove(i));
}
int[] array = new int[n - m];
for (int i = 0; i < (n - m); i++) {
array[i] = arrayList.get(i);
}
System.out.println("Array is: " + Arrays.toString(array));
findMissingNumbers(n, array);
}
}
n이 8이고 숫자의 범위는 0-8 이고이 예에서 숫자는 다음과 같이 9 개 개 숫자 모두의 이진 표현을 수 있습니다. 0000 0001 0010 0011 0100 0101 0110 0111 1000
위의 순서에서는 누락 된 숫자가없고 각 열에서 0과 1의 수가 일치하지만 1 개의 제거하자마자 3을 말하면 열 전체에 값 0과 1의 수에 균형을 맞습니다. 열에있는 0의 수가 <= 인 경우 누락 된 숫자는 비트 위치에서 0이됩니다. 숫자 0의 수가>이 비트 위치에있는 1의 수이면이 비트 위치는 1이됩니다. 우리는 왼쪽에서 오른쪽으로 비트를 테스트하고 각 반복에서 다음 비트 테스트를 배열의 절반을 버립니다. 홀수 배열 값 또는 짝수 배열 값은 부족한 비트에 따라 각 반복에서 버려입니다. 의 위에.
아래 솔루션은 C ++에 있습니다.
int getMissingNumber(vector<int>* input, int bitPos, const int startRange)
{
vector<int> zeros;
vector<int> ones;
int missingNumber=0;
//base case, assume empty array indicating start value of range is missing
if(input->size() == 0)
return startRange;
//if the bit position being tested is 0 add to the zero's vector
//otherwise to the ones vector
for(unsigned int i = 0; i<input->size(); i++)
{
int value = input->at(i);
if(getBit(value, bitPos) == 0)
zeros.push_back(value);
else
ones.push_back(value);
}
//throw away either the odd or even numbers and test
//the next bit position, build the missing number
//from right to left
if(zeros.size() <= ones.size())
{
//missing number is even
missingNumber = getMissingNumber(&zeros, bitPos+1, startRange);
missingNumber = (missingNumber << 1) | 0;
}
else
{
//missing number is odd
missingNumber = getMissingNumber(&ones, bitPos+1, startRange);
missingNumber = (missingNumber << 1) | 1;
}
return missingNumber;
}
반복 할 때마다 입력 공간을 2만큼 줄입니다. 즉, N, N / 2, N / 4 ... = O (log N), 공간 O (N)
//Test cases
[1] when missing number is range start
[2] when missing number is range end
[3] when missing number is odd
[4] when missing number is even
PHP를 솔루션 솔루션 $ n = 100 ;
$n*($n+1)/2 - array_sum($array) = $missing_number
및 array_search($missing_number)누락 된 숫자의 보강을 줄 것이다
여기서 프로그램 소요 시간 복잡도는 O (logn)이고 공간 복잡도는 O (logn)입니다.
public class helper1 {
public static void main(String[] args) {
int a[] = {1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12};
int k = missing(a, 0, a.length);
System.out.println(k);
}
public static int missing(int[] a, int f, int l) {
int mid = (l + f) / 2;
//if first index reached last then no element found
if (a.length - 1 == f) {
System.out.println("missing not find ");
return 0;
}
//if mid with first found
if (mid == f) {
System.out.println(a[mid] + 1);
return a[mid] + 1;
}
if ((mid + 1) == a[mid])
return missing(a, mid, l);
else
return missing(a, f, mid);
}
}
public class MissingNumber {
public static void main(String[] args) {
int array[] = {1,2,3,4,6};
int x1 = getMissingNumber(array,6);
System.out.println("The Missing number is: "+x1);
}
private static int getMissingNumber(int[] array, int i) {
int acctualnumber =0;
int expectednumber = (i*(i+1)/2);
for (int j : array) {
acctualnumber = acctualnumber+j;
}
System.out.println(acctualnumber);
System.out.println(expectednumber);
return expectednumber-acctualnumber;
}
}
전체 공식 사용,
class Main {
// Function to ind missing number
static int getMissingNo (int a[], int n) {
int i, total;
total = (n+1)*(n+2)/2;
for ( i = 0; i< n; i++)
total -= a[i];
return total;
}
/* program to test above function */
public static void main(String args[]) {
int a[] = {1,2,4,5,6};
int miss = getMissingNo(a,5);
System.out.println(miss);
}
}
참조 http://www.geeksforgeeks.org/find-the-missing-number/
simple solution with test data :
class A{
public static void main(String[] args){
int[] array = new int[200];
for(int i=0;i<100;i++){
if(i != 51){
array[i] = i;
}
}
for(int i=100;i<200;i++){
array[i] = i;
}
int temp = 0;
for(int i=0;i<200;i++){
temp ^= array[i];
}
System.out.println(temp);
}
}
//Array is shorted and if writing in C/C++ think of XOR implementations in java as follows.
int num=-1;
for (int i=1; i<=100; i++){
num =2*i;
if(arr[num]==0){
System.out.println("index: "+i+" Array position: "+ num);
break;
}
else if(arr[num-1]==0){
System.out.println("index: "+i+ " Array position: "+ (num-1));
break;
}
}// use Rabbit and tortoise race, move the dangling index faster,
//learnt from Alogithimica, Ameerpet, hyderbad**
배열이 무작위로 채워지면 기껏해야 O (n) 배열이 선형 검색을 수행 할 수 있습니다. 숫자가 오름차순 / 내림차순이라는 점을 감안할 때 giri가 빠른 정렬과 분할 및 정복 접근 방식으로 O (log n)의 적절한 것을 개선 할 수 있지만.
이제 나는 Big O 표기법에 너무 예리하지만 (Java에서) 같은 것을 할 수 없습니다.
for (int i = 0; i < numbers.length; i++) {
if(numbers[i] != i+1){
System.out.println(i+1);
}
}
여기서 숫자는 1-100 사이의 숫자가있는 배열입니다. 질문을 읽었을 때 누락 된 숫자를 언제 써야하는지 말하지 않습니다.
또는 i + 1의 값을 다른 배열에 던지고 반복 후에 출력 할 수 있다면.
물론 시간과 공간의 규칙을 따르지 않을 수도 있습니다. 내가 말했듯이. Big O를 강하게 닦아야합니다.
======== 정렬 된 배열을위한 가장 간단한 솔루션 ===========
public int getMissingNumber(int[] sortedArray)
{
int missingNumber = 0;
int missingNumberIndex=0;
for (int i = 0; i < sortedArray.length; i++)
{
if (sortedArray[i] == 0)
{
missingNumber = (sortedArray[i + 1]) - 1;
missingNumberIndex=i;
System.out.println("missingNumberIndex: "+missingNumberIndex);
break;
}
}
return missingNumber;
}
또 다른 숙제 질문입니다. 순차 검색이 최선입니다. Java 솔루션의 경우 독자를위한 연습이라고 생각하십시오. :피
'ProgramingTip' 카테고리의 다른 글
| 의미와 구문이 동일합니까? (0) | 2020.11.10 |
|---|---|
| RVM없이 Ubuntu에 Ruby 2를 설치하는 방법 (0) | 2020.11.09 |
| 조건에 따라 목록에서 항목 제거 (0) | 2020.11.09 |
| Android FragmentTransaction 사용자 정의 애니메이션 (알 수없는 애니메이터 이름 : 번역) (0) | 2020.11.09 |
| NSArray를 반복하는 쉬운 방법이 거꾸로? (0) | 2020.11.09 |