01/10/2018, 16:33

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

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.

codility.com

Codility – Industry Leading Tech Recruiting Platform

Codility streamlines and accelerates tech recruiting. Codility automates sourcing, screening and interviewing, reducing recruiting costs and improving hiring results.

Nguyễn Đình Anh viết 18:37 ngày 01/10/2018

sắp xếp mảng tăng dần

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.

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

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

thì xuất ra 1 còn không là -1

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

mmmm viết 18:42 ngày 01/10/2018

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

Nguyễn Đình Anh viết 18:35 ngày 01/10/2018

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

rogp10 viết 18:49 ngày 01/10/2018

Cái này không đúng nhé, in a non-decreasing order được sắp xếp theo thứ tự ngẫu nhiên

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

Nguyễn Đình Anh viết 18:40 ngày 01/10/2018

Cảm ơn @rogp10
Azzz, mình bị nhầm thành “not in order” 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

mmmm viết 18:43 ngày 01/10/2018

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

Nguyễn Đình Anh viết 18:48 ngày 01/10/2018

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 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

rogp10 viết 18:40 ngày 01/10/2018

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 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

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

Nguyễn Đình Anh viết 18:36 ngày 01/10/2018

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

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

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: