Hướng dẫn degree of an array hackerrank solution python - mức độ của một mảng giải pháp hackerrank python

Permalink

Không thể lấy lại những người đóng góp tại thời điểm này

Tệp này chứa văn bản unicode hai chiều có thể được giải thích hoặc biên dịch khác với những gì xuất hiện dưới đây. Để xem xét, hãy mở tệp trong một trình soạn thảo cho thấy các ký tự Unicode ẩn. Tìm hiểu thêm về các ký tự unicode hai chiều

Chúng tôi đã đưa ra mảng như A = [1,2,3,4,1,2,1,1,1,2,2] vì vậy chúng tôi đã tìm thấy phần tử trùng lặp khỏi mảng và tách mảng như [1,1,1 , 1,1] và [2,2,2,2] và chỉ in chiều dài lớn nhất của mảng nên ở đây độ dài lớn nhất là 5 là [1,1,1,1,1]. Tôi cố gắng sử dụng itertools nhưng không tập thể dục.

Đầu vào là A = [1,2,3,1,1,1,1,2,2,2]]

O/P nên là 5.

import itertools

my_list = [1,2,2,2,1,1,2,2,2,3,4]





num1=[]

for a, b in itertools.combinations(my_list,2):
    if a == b:
        num1.append(b)

print(num1)
max_ele=max(num1)
print(max_ele)
print(num1.count(max_ele))

CẬP NHẬT {mảng [i], đếm [mảng [i]]+1} trong đếm.degree of this array is defined as the maximum frequency of any one of its elements.

Lấy một biến ANS = n.

Đối với mỗi ARR [i] có số lượng [mảng [i]] == k:

Input: nums = [1,2,2,3,1]
Output: 2
Explanation: 
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.

Ans = min (phải [mảng [i]]-trái [mảng [i]]+1, ans)

Input: nums = [1,2,2,3,1,4,2]
Output: 6
Explanation: 
The degree is 3 because the element 2 is repeated 3 times.
So [2,2,3,1,4,2] is the shortest subarray, therefore returning 6.

Constraints:

• Ví dụ về mức độ của một mảng
• Ở đây chúng tôi có hai yếu tố có tần số tối đa là 3, đây là 1 và 2.

• Báo cáo vấn đề
• Cách tiếp cận 1: Sử dụng tìm kiếm nhị phân
  • Thuật toán
  • Thực hiện
    • Chương trình C ++ cho mức độ của một mảng
  • Sự phức tạp
• Cách tiếp cận 2: Sử dụng băm
  • Thuật toán
  • Thực hiện
  • Thực hiện
    • Chương trình C ++ cho mức độ của một mảng
    • Sự phức tạp
  • Sự phức tạp

Báo cáo vấn đề

Cách tiếp cận 1: Sử dụng tìm kiếm nhị phânDegree of an array problem we have given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.

Thuật toán

Input: [1, 2, 2, 3, 1]

Output: 2

Cách tiếp cận 1: Sử dụng tìm kiếm nhị phân

Thuật toán

Thực hiện

Chương trình C ++ cho mức độ của một mảng

Sự phức tạp

Cách tiếp cận 2: Sử dụng băm

Thuật toán

1. Thực hiện
2. Chương trình C ++ cho mức độ của một mảng
3. Sự phức tạp
   • Cách tiếp cận 2: Sử dụng băm
   • Ví dụ về mức độ của một mảng
   • Chương trình C ++ cho mức độ của một mảng
4. Chương trình Java cho mức độ của một mảng

Thực hiện

Chương trình C ++ cho mức độ của một mảng

#include
using namespace std;
int findDegree(vector& v, int k){
    unordered_map m;
    int ans=0;
    for(int i=0;i& nums) {
    int k=findDegree(nums,nums.size());
    int l=k,r=nums.size(),m,ans=nums.size();
    while(l<=r){
        m=l+(r-l)/2;
        int x=findDegree(nums,m);
        if(x==k){
            ans=m;
            r=m-1;
        }
        else{
            l=m+1;
        }
    }
    return ans;
}
int main(){
    int n;
    cin>>n;
    vector arr(n);
    for(int i=0;i>arr[i];
    }
    cout<<"The smallest possible length of a subarray of the given array, that has same degree is: "<
7 
1 2 2 3 1 4 2
The smallest possible length of a subarray of the given array, that has same degree is: 6
Sự phức tạp
Cách tiếp cận 2: Sử dụng băm O(nlogn), we do logn search on size and in each search, we are traversing the array once.
Ví dụ về mức độ của một mảng O(1), no extra space required.



Cách tiếp cận 2: Sử dụng băm
Ví dụ về mức độ của một mảng
Thuật toán
Thực hiện
Chương trình C ++ cho mức độ của một mảng
Sự phức tạp
Cách tiếp cận 2: Sử dụng băm
Ví dụ về mức độ của một mảng
Chương trình C ++ cho mức độ của một mảng
Chương trình Java cho mức độ của một mảng
Trong mức độ của một vấn đề mảng, chúng tôi đã đưa ra một loạt các số nguyên không âm tính, mức độ của mảng này được định nghĩa là tần số tối đa của bất kỳ một trong các yếu tố của nó.
Chương trình Java cho mức độ của một mảng
Thực hiện
Chương trình C ++ cho mức độ của một mảng
Sự phức tạp
Cách tiếp cận 2: Sử dụng băm
Thực hiện
Chương trình C ++ cho mức độ của một mảng
#include
using namespace std;
int findShortestSubArray(vector& nums){
   unordered_map left, right, count;
   int degree = 0;
    for (int i = 0; i < nums.size(); i++) {
        int x = nums[i];
        if (left.find(x)==left.end()) 
            left.insert({x,i});
        right[x]=i;
        count[x]++;
        degree=max(degree,count[x]);
    }
    int ans = nums.size();
    for (auto &it:count) {
        if (it.second == degree) {
            ans = min(ans, right[it.first] - left[it.first] + 1);
        }
    }
    return ans;
}
int main(){
    vector arr={1, 2, 2, 3, 1, 4, 2};
    cout<<"The smallest possible length of a subarray of the given array, that has same degree is: "<
The smallest possible length of a subarray of the given array, that has same degree is: 6
Sự phức tạp
import java.util.*; 
public class Main
{
    public static int findShortestSubArray(int[] nums) {
        Map left = new HashMap(),
            right = new HashMap(), count = new HashMap();

        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            if (left.get(x) == null) left.put(x, i);
            right.put(x, i);
            count.put(x, count.getOrDefault(x, 0) + 1);
        }

        int ans = nums.length;
        int degree = Collections.max(count.values());
        for (int x: count.keySet()) {
            if (count.get(x) == degree) {
                ans = Math.min(ans, right.get(x) - left.get(x) + 1);
            }
        }
        return ans;
    }
  public static void main(String[] args) {
      int[] arr={1,2,3,4,4,3,2,2,4};
    System.out.println("The smallest possible length of a subarray of the given array, that has same degree is: "+findShortestSubArray(arr));
  }
}
The smallest possible length of a subarray of the given array, that has same degree is: 6
Sự phức tạp
Cách tiếp cận 2: Sử dụng băm O(n) as we are traversing the array and map at once.
Ví dụ về mức độ của một mảng O(n) as we used three hashmaps.
Chương trình C ++ cho mức độ của một mảng
 

			
Làm thế nào để bạn tìm thấy mức độ của một mảng?
			
Mức độ của một mảng trong C ++, chúng ta phải tìm độ dài nhỏ nhất có thể của một subarray tiếp giáp của nums, có cùng mức độ với nums.Vì vậy, nếu đầu vào giống như [1,2,2,3,1], thì đầu ra sẽ là 2, điều này là do mảng đầu vào có mức độ 2 vì cả hai phần tử 1 và 2 đều xuất hiện hai lần.find the smallest possible length of a contiguous subarray of nums, that has the same degree as nums. So, if the input is like [1,2,2,3,1], then the output will be 2, this is because the input array has a degree of 2 because both elements 1 and 2 appear twice.
		
			
Một mức độ của một mảng là gì?
			
Với một mảng không trống của số nguyên không âm, mức độ của mảng này được định nghĩa là tần số tối đa của bất kỳ một trong các yếu tố của nó.Nhiệm vụ của bạn là tìm độ dài nhỏ nhất có thể của một con nums (tiếp giáp) của nums, có cùng mức độ với nums.the maximum frequency of any one of its elements. Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.
		
			
Mảng phụ là gì?
			
Một Subarray là một phần tiếp giáp của mảng, tức là, Subarray là một mảng nằm trong một mảng khác.Nói chung, đối với một mảng có kích thước n, có n*(n+1)/2 subarrays không trống.Ví dụ, hãy xem xét mảng [1, 2, 3, 4], có 10 mảng con không trống.an array that is inside another array. In general, for an array of size n, there are n*(n+1)/2 non-empty subarrays. For example, Consider the array [1, 2, 3, 4], There are 10 non-empty sub-arrays.