1538.txt

We have an integer array nums, where all the integers in nums are 0 or 1. You will not be given direct access to the array, instead, you will have an API ArrayReader which have the following functions:

int query(int a, int b, int c, int d): where 0 <= a < b < c < d < ArrayReader.length(). The function returns the distribution of the value of the 4 elements and returns:
4 : if the values of the 4 elements are the same (0 or 1).
2 : if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.
0 : if two element have a value equal to 0 and two elements have a value equal to 1.
int length(): Returns the size of the array.
You are allowed to call query() 2 * n times at most where n is equal to ArrayReader.length().

Return any index of the most frequent value in nums, in case of tie, return -1.

Follow up: What is the minimum number of calls needed to find the majority element?





思路：想如何去分类


/**
 * // This is the ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface ArrayReader {
 *   public:
 *     // Compares 4 different elements in the array
 *     // return 4 if the values of the 4 elements are the same (0 or 1).
 *     // return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.
 *     // return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.
 *     public int query(int a, int b, int c, int d);
 *
 *     // Returns the length of the array
 *     public int length();
 * };
 */

class Solution {
    public int guessMajority(ArrayReader reader) {
        
        int n=reader.length();

        int start=reader.query(0,1,2,3);

        int i1=3;int i2=-1;
        int group1=1,group2=0;

        //假设 index3 是group1      

        for(int i=4;i<n;i++){
            int q=reader.query(0,1,2,i);
            if(q==start)group1++;
            else {
                i2=i;
                group2++;
            }
        }
//0,0,1,0,1

        //再看前面3个值

        int sudo=reader.query(0,1,2,4);
        //test 0
        if(reader.query(1,2,3,4)==sudo){
            group1++;
        }else{
            group2++;
            i2=0;
        }

        //test 2
        if(reader.query(0,1,3,4)==sudo){
            group1++;
        }else{
           group2++;i2=2;
        }

        //test1
        if(reader.query(0,2,3,4)==sudo){
            group1++;
        }else{
            group2++;i2=1;
        }

        if(group1==group2)return -1;
        if(group1>group2)return i1;
        return i2;

    }
}


优化版本：
1.如果知道其中两个数是一样的话，我们可以两个两个的看
2. 最终会call n/2 次

代码：
/**
 * // This is the ArrayReader's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface ArrayReader {
 *   public:
 *     // Compares 4 different elements in the array
 *     // return 4 if the values of the 4 elements are the same (0 or 1).
 *     // return 2 if three elements have a value equal to 0 and one element has value equal to 1 or vice versa.
 *     // return 0 : if two element have a value equal to 0 and two elements have a value equal to 1.
 *     public int query(int a, int b, int c, int d);
 *
 *     // Returns the length of the array
 *     public int length();
 * };
 */

class Solution {
    public int guessMajority(ArrayReader reader) {
        
        int n=reader.length();
        //再看前面3个值

        int sudo=reader.query(0,1,2,4);
        List<Integer>list1=new ArrayList<>();
        List<Integer>list2=new ArrayList<>();
        list1.add(3);
        
        //test 0
        if(reader.query(1,2,3,4)==sudo){
            list1.add(0);
        }else{
            list2.add(0);
        }

        //test1
        if(reader.query(0,2,3,4)==sudo){
            list1.add(1);
        }else{
            list2.add(1);
        }
        //test 2
        if(reader.query(0,1,3,4)==sudo){
             list1.add(2);
        }else{
             list2.add(2);
        }

        Collections.sort(list1);
        Collections.sort(list2);

        //cnt1 : count for 1 and two
        boolean isone=false;
        int one=-1,two=-1,three=-1;;
        int cnt1=0,cnt2=0;
        if(list1.size()>=2){
            one=list1.get(0);
            two=list1.get(1);
            isone=true;
            cnt1=list1.size();
            cnt2=list2.size();
        }else{
            one=list2.get(0);
            two=list2.get(1);
            cnt1=list2.size();
            cnt2=list1.size();
        }
        
        for(int i=4;i<n;i+=2){
            if(i+1>=n)break;
            int q=reader.query(one,two,i,i+1);
            if(q==4){
                cnt1+=2;
            }
            else if(q==2){
                cnt1++;
                cnt2++;
            }
            else if(q==0){
                cnt2+=2;
                three=i;
            }
        } 


        if(n%2==1){
            int q=reader.query(0,1,2,n-1);
            int start=reader.query(0,1,2,3);
            if(isone){//3 is cnt1
                if(q==start)cnt1++;
                else {
                    three=n-1;
                    cnt2++;
                }

            }else{
                if(q==start){
                    cnt2++;
                    three=n-1;
                }
                else cnt1++;
            }
        }


        if(cnt1==cnt2)return -1;
        if(cnt1>cnt2)return one;
        return three;

    }
}