1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | #include <stdio.h> int main() { int count = 0, input = 0; int ary[10] = {0, 1, 2, 3, 4, 4, 3, 2, 5, 6}; printf("Input a number : "); scanf("%d", &input); for(int i = 0; i < sizeof(ary); i++) { if (input == ary[i]) { count++; } // end of if } // end of for printf("The number of the same number which you input (%d) in Array ary is %d \n", input, count - 1); } | cs |
⚠️AdBlock이 감지되었습니다. 원할한 페이지 표시를 위해 AdBlock을 꺼주세요.⚠️
중복을 포함하는 어레이된 정수 어레이이 주어지면 주어진 숫자의 발생 횟수를 계산합니다. 어레이에서 요소를 찾을 수 없는 경우 해당 요소도 보고합니다.
예를 들어,
Input: nums[] = [2, 5, 5, 5, 6, 6, 8, 9, 9, 9]
target = 5
Output: Target 5 occurs 3 times
Input: nums[] = [2, 5, 5, 5, 6, 6, 8, 9, 9, 9]
target = 6
Output: Target 6 occurs 2 times
이 문제를 연습
간단한 해결책은 어레이에서 선형 검색을 실행하고 주어진 요소의 발생 횟수를 계산하는 것입니다. 이 접근 방식의 문제는 최악의 시간 복잡도가 O(n), 어디 n 입력의 크기입니다. 이 솔루션은 또한 입력이 정렬된다는 사실을 이용하지 않습니다.
또 다른 솔루션은 이진 검색 주어진 어레이된 어레이에서 주어진 숫자가 나타나는 인덱스를 찾습니다. target. 어레이이 어레이되기 때문에 모든 발생 target 인접하게 됩니다. 따라서 선형 스캔을 실행하여 target 찾은 인덱스의 왼쪽과 오른쪽. 이 솔루션의 최악의 시간 복잡도는 다음과 같습니다. O(n). 최악의 경우는 모든 어레이 요소가 주어진 숫자와 같을 때 발생합니다.
우리는 이 문제를 쉽게 해결할 수 있습니다. O(log(n)) 시간 이진 검색 알고리즘 수정. 아이디어는 주어진 숫자의 첫 번째와 마지막 발생의 인덱스를 찾고 두 인덱스의 차이보다 하나를 더 반환하는 것입니다. 우리는 이미 방법과 숫자의 처음과 마지막 항목 찾기 안에 O(log(n)) 이전 포스트의 시간.
알고리즘은 C, Java 및 Python에서 다음과 같이 구현할 수 있습니다.
C
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | #include <stdio.h> // 주어진 숫자의 첫 번째 또는 마지막 발생을 찾는 함수 // 어레이된 정수 어레이. `searchFirst`가 true이면 반환 // 숫자의 첫 번째 발생; 그렇지 않으면 마지막 항목을 반환합니다. intbinarySearch(int nums[],intn,int target,intsearchFirst) { // 검색 공간은 nums[low…high]입니다. intlow=0,high= n-1; // 결과를 -1로 초기화 int result=-1; // 검색 공간이 소진될 때까지 루프 while(low<=high) { // 검색 공간에서 중간 값을 찾아 대상과 비교합니다. intmid=(low +high)/2; // 타겟이 발견되면 결과 업데이트 if(target==nums[mid]) { result=mid; // 왼쪽으로 계속 검색(하위 인덱스) if(searchFirst){ high=mid-1; } // 오른쪽으로 계속 검색(높은 인덱스) else{ low=mid+1; } } // 타겟이 중간 요소보다 작으면 오른쪽 절반을 버립니다. else if(target<nums[mid]) { high=mid-1; } // 타겟이 중간 요소보다 크면 왼쪽 절반을 버립니다. else{ low=mid+1; } } // 찾은 인덱스를 반환하거나 요소가 없으면 -1을 반환합니다. return result; } intmain(void) { intnums[]={2, 5,5,5,6, 6,8,9,9, 9}; inttarget=5; intn= sizeof(nums)/sizeof(nums[0]); // 첫 번째 발생에 대해 값 1을 전달합니다. intfirst= binarySearch(nums,n,target, 1); // 마지막 발생에 대해 값 0을 전달합니다. intlast =binarySearch(nums,n,target, 0); intcount=last -first+1; if (first!=-1){ printf("Element %d occurs %d times",target,count); } else{ printf("Element not found in the array"); } return0; } |
다운로드 코드 실행
결과:
Element 5 occurs 3 times
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | classMain { // 주어진 숫자의 첫 번째 또는 마지막 발생을 찾는 함수 // 어레이된 정수 어레이. `searchFirst`가 true이면 반환 // 숫자의 첫 번째 발생; 그렇지 않으면 마지막 항목을 반환합니다. publicstaticint binarySearch(int[]nums,int target,booleansearchFirst) { // 검색 공간은 nums[left… right] intleft=0; intright=nums.length- 1; // 결과를 -1로 초기화 intresult =-1; // 검색 공간이 소진될 때까지 루프 while (left<=right) { // 검색 공간에서 중간 값을 찾아 대상과 비교합니다. intmid=(left +right)/2; // 타겟이 발견되면 결과 업데이트 if(target== nums[mid]) { result=mid; // 왼쪽으로 계속 검색(하위 인덱스) if(searchFirst){ right =mid-1; } // 오른쪽으로 계속 검색(높은 인덱스) else{ left=mid+1; } } // 타겟이 중간 요소보다 작으면 오른쪽 절반을 버립니다. elseif(target< nums[mid]){ right =mid-1; } // 타겟이 중간 요소보다 크면 왼쪽 절반을 버립니다. else{ left =mid+1; } } // 찾은 인덱스를 반환하거나 요소가 없으면 -1을 반환합니다. returnresult; } publicstaticvoid main(String[]args) { int[]nums={2, 5,5,5,6, 6,8,9,9, 9}; inttarget= 5; // 첫 번째 항목에 대해 true를 전달합니다. intfirst =binarySearch(nums,target,true); // 마지막 발생에 대해 false를 전달합니다. intlast=binarySearch(nums,target,false); intcount=last-first +1; if(first!= -1){ System.out.println("Element "+target +" occurs "+count+" times"); } else{ System.out.println("Element not found in the array"); } } } |
다운로드 코드 실행
결과:
Element 5 occurs 3 times
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | # 주어진 숫자의 첫 번째 또는 마지막 발생을 찾는 함수 # 정렬된 정수 목록입니다. `searchFirst`가 true이면 반환 # 숫자의 첫 번째 발생; 그렇지 않으면 마지막 항목을 반환합니다. defbinarySearch(nums, target,searchFirst): # 검색 공간은 nums[left…right]입니다. (left,right)=(0, len(nums)-1) #는 결과를 -1로 초기화합니다. result=-1 # 검색 공간이 소진될 때까지 # 루프 while left<=right: # 검색 공간에서 중간값을 찾아 타겟과 비교 mid=(left+right) //2 # 대상이 발견되면 결과 업데이트 if target==nums[mid]: result=mid # 왼쪽(하위 인덱스)으로 계속 검색 ifsearchFirst: right= mid-1 # 오른쪽으로 계속 검색(높은 인덱스) else: left=mid+ 1 # 대상이 중간 요소보다 작으면 오른쪽 절반을 버립니다. eliftarget< nums[mid]: right= mid-1 # 대상이 중간 요소보다 크면 왼쪽 절반을 버립니다. else: left=mid+1 #는 찾은 인덱스를 반환하거나 요소가 없으면 -1을 반환합니다. returnresult if__name__== '__main__': nums=[2, 5,5,5,6, 6,8,9,9, 9] target=5 first =binarySearch(nums,target, True) #는 첫 번째 발생에 대해 true를 통과합니다. last= binarySearch(nums,target,False) #는 마지막 발생에 대해 false를 전달합니다. count=last-first +1 iffirst!= -1: print(f'Element {target} occurs {count} times') else: print('Element found not in the list') |
다운로드 코드 실행
결과:
Element 5 occurs 3 times
위 솔루션의 시간 복잡도는 O(log(n)) 추가 공간이 필요하지 않습니다. n 입력의 크기입니다.
참조:
읽어 주셔서 감사합니다.
우리의 온라인 컴파일러 C, C++, Java, Python, JavaScript, C#, PHP 및 기타 널리 사용되는 프로그래밍 언어를 사용하여 주석에 코드를 게시합니다.
우리처럼? 우리를 친구에게 소개하고 우리가 성장할 수 있도록 도와주세요. 행복한 코딩 :)