Tìm số leader trong mảng không giảm

#1

Chào mọi người, em có đề sau, vì em rất yếu tiếng anh , em google thì hiểu như sau có đúng hay không ạ: sắp xếp mảng tăng dần, tìm số leader, số đó là số xuất hiện nhiều lần nhất trong mảng nếu số leader có số lần xuất hiện lớn hơn phần tử mảng/2 thì xuất ra 1 còn không là -1

A non-empty array A consisting of N integers and sorted in a non-decreasing order (i.e. A[0] ≤ A[1] ≤ … ≤ A[N−1]) is given. The leader of this array is the value that occurs in more than half of the elements of A.

You are given an implementation of a function:

class Solution { public int solution(int[] A); }

that, given a non-empty array A consisting of N integers, sorted in a non-decreasing order, returns the leader of array A. The function should return −1 if array A does not contain a leader.

For example, given array A consisting of ten elements such that:

A[0] = 2
A[1] = 2
A[2] = 2
A[3] = 2
A[4] = 2
A[5] = 3
A[6] = 4
A[7] = 4
A[8] = 4
A[9] = 6
the function should return −1, because the value that occurs most frequently in the array, 2, occurs five times, and 5 is not more than half of 10.

Given array A consisting of five elements such that:

A[0] = 1
A[1] = 1
A[2] = 1
A[3] = 1
A[4] = 50
the function should return 1.

The attached code is still incorrect on some inputs. Despite the error(s), the code may produce a correct answer for the example test cases. The goal of the exercise is to find and fix the bug(s) in the implementation. You can modify at most three lines.

Assume that:

N is an integer within the range [1…100,000];
each element of array A is an integer within the range [0…2,147,483,647];
array A is sorted in non-decreasing order.
In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.
Copyright 2009–2018 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

#3

Cái này không đúng nhé, in a non-decreasing order được sắp xếp theo thứ tự không giảm dần.

Cái này thì đúng rồi :slight_smile:

Là in ra số leader nhé bạn :slight_smile:

#4

vậy mình có được sắp xếp lại mảng cho tăng dần ko ạ, à mình sẽ code xong nhờ bạn góp ý cho thuật toán với, mình code còn yếu

#5

Đây chỉ là tìm số trùng nhau thôi nên mình nghĩ là không cần đâu :slight_smile:

1 Like
#6

:expressionless: non-decreasing là không giảm đó.

Bài này là sửa code mà (!), nên có kèm thuật toán trong đó (sắp xếp rồi soi). Riêng bài này thì cứ làm theo vậy :smiley:

2 Likes
#7

Cảm ơn @rogp10
Azzz, mình bị nhầm thành “not in order” :frowning: Xin lỗi bạn nhé @Tran_Thi_My_Hoa

Mình vẫn muốn bạn ý nghĩ trước xong mới gợi ý thuật toán sau :slight_smile:

2 Likes
#8

Mình có code như vầy, mọi người cho biết cần sửa chỗ nào với ko ạ.

#9

Lần sau post code lên chứ đừng chụp màn hình bạn nhé, nhớ Mark down code nhé.

Vì số leader là số có tần suất xuất hiện trong mảng > 1/2 số phần tử trong mảng, nên số leader chỉ có thể nằm trong nửa đầu của mảng thôi :slight_smile: Thuật toán của mình là:
B1: Chạy một vòng for từ đầu đến giữa mảng
B2: Nếu A[i] == A[i + (A.length() / 2) ] thì đó sẽ là leader

#10

Dự là nhiều false-positive lắm :smiley: [spoiler] nhưng mà ai đưa ra thuật người đó phải chứng minh.[/spoiler]

2 Likes
#11

Mình mới nghĩ ra cách đó thôi :slight_smile: Nếu bạn có cách khác hay hơn thì mong được chỉ giáo :slight_smile:

Còn về việc chứng minh thì đây :slight_smile:

public class Find_Leader 
{
    public static void main(String[] args) 
    {
        // Test 1
        int[] case_1 = {2,2,2,2,2,3,4,4,4,6};
        System.out.println("Case 1: ");
        System.out.println("Leader: " + my_Solution(case_1));        
        System.out.println("=============================");
        
        // Test 2
        int[] case_2 = {1,1,1,1,50};
        System.out.println("Case 2: ");
        System.out.println("Leader: " + my_Solution(case_2));        
    }
    
    public static int my_Solution(int[] A)
    {
        int output = -1;      
        
        for(int i = 0; i < (A.length / 2); i++)
        {
            if(A[i] == A[i + (A.length / 2)])
            {
                output = A[i];
                break;
            }
        }
        
        return output;
    }
}

Đây là Output:

1 Like
#12

wow, thật ngưỡng mộ.

1 Like
#13

Ừ nhỉ, mảng không giảm mà có a[i] = a[i+n/2] thì đúng nó rồi :smiley:

Mà ý tui là dùng lí luận ấy.

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?