Hi, this is for an assignment I have to turn in on monday, but I don\'t have tim

Question

Hi, this is for an assignment I have to turn in on monday, but I don't have time since I have a big test coming up on Tuesday, please could you submit the answer to my email to make it private? please

needed_sites@outlook.com

Thank you! Thumbs up waiting :)

btw don't use maps. This is java

Given an array A of n integers, a leader element of the array A is the element that appears
more than half of the time in A.
Implement in Java an O(n) worst-case algorithm that uses a stack
static int leader(int[] A)
to find a leader element and return the index (any) of the leader in A. The program must
returns -1 if no leader element exists.
Examples:
int[] a = {23, 23, 67, 23, 67, 23, 45}; ====> leader(a) = 5
int[] a = {23, 24, 67, 23, 67, 23, 45}; ====> leader(a) = -1

Explanation / Answer

/**

*
* @author Sam
*/
public class Leader {
     static int leader(int[] A){
         class Node {
             int num, count;
             Node next;
         }
         int maxCount = 0;
         int maxCountNum = 0;
         Node[] hashTable = new Node[A.length * 100];
         for (int i = 0; i< A.length; i++ ){
             int hashCode = A[i]%100;
             Node tmp = hashTable[hashCode];
             while (tmp!= null) {
                 if (tmp.num == A[i]) {
                     tmp.count++;
                     if (tmp.count > maxCount) {
                         maxCount = tmp.count;
                         maxCountNum = tmp.num;
                     }
                     break;
                 }
                 tmp = tmp.next;
             }
             if (tmp == null) {
                 tmp = new Node();
                 tmp.num = A[i];
                 tmp.count = 1;
                 tmp.next = hashTable[hashCode];
                 if (maxCount == 0) {
                     maxCountNum = tmp.num;
                     maxCount = 1;
                 }
                 hashTable[hashCode] = tmp;
             }
         }
         if (maxCount > A.length/2)
             return maxCountNum;
         return -1;
     }
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.