Find majority element in an array Input: L[1,..., n] as input list containing n real numbers...

   

Transcribed Image Text:

Find majority element in an array Input: L[1,..., n] as input list containing n real numbers Output: True or False. If true, also returning the majority element 1: c = 0, v = L[1] 2: for i=1,2,..., n do 3: if c = 0 then 4: 5: 6: v = L[i] end if if v == L[i] then c = c + 1 7: 8: 9: 10: 11: end for 12: Future steps else c=c-1 end if We want to check if there is an element occurs more than 22 times in an array containing n elements, assuming only equality checks are allowed. (a) Algo. 1 is part of the required algorithm. What is the time complexity now? (b) Make the algorithm complete by adding a few more lines to substitute the underlined text. Your modification should NOT change the time complexity. Be sure to return things as indicated. Find majority element in an array Input: L[1,..., n] as input list containing n real numbers Output: True or False. If true, also returning the majority element 1: c = 0, v = L[1] 2: for i=1,2,..., n do 3: if c = 0 then 4: 5: 6: v = L[i] end if if v == L[i] then c = c + 1 7: 8: 9: 10: 11: end for 12: Future steps else c=c-1 end if We want to check if there is an element occurs more than 22 times in an array containing n elements, assuming only equality checks are allowed. (a) Algo. 1 is part of the required algorithm. What is the time complexity now? (b) Make the algorithm complete by adding a few more lines to substitute the underlined text. Your modification should NOT change the time complexity. Be sure to return things as indicated.

Answer rating: 100% (QA)

The provided images show an algorithm that is used to find the majority element in an array if such ... View the full answer