Generating Permutations Time Complexity:(nn!) Space Complexity:(n)
Generating Permutations ◼ Time Complexity: (nn!) ◼ Space Complexity: (n)
Finding the Majority Eement Let A[1...n]be a sequence of integers.An integer a in A is called the majority if it appears more than //2 times in 4. For example: Sequence 1,3,2,3,3,4,3:3 is the majority element since 3 appears 4 times which is more than Ln/2 √ Sequence 1,3,2,3,3,4:3 is not the majority element since 3 appears three times which is equal to Ln/2,but not more than [n/2
Finding the Majority Element ◼ Let A[1…n] be a sequence of integers. An integer a in A is called the majority if it appears more than n/2 times in A. ◼ For example: ✓ Sequence 1, 3, 2, 3, 3, 4, 3: 3 is the majority element since 3 appears 4 times which is more than n/2 ✓ Sequence 1, 3, 2, 3, 3, 4: 3 is not the majority element since 3 appears three times which is equal to n/2, but not more than n/2
Finding the Majority Eement If two different elements in the original sequence are removed,then the majority in the original sequence remains the majority in the new sequence. The above observation suggests the following procedure for finding an element that is candidate for being the majority
Finding the Majority Element ◼ If two different elements in the original sequence are removed, then the majority in the original sequence remains the majority in the new sequence. ◼ The above observation suggests the following procedure for finding an element that is candidate for being the majority
Finding the Majority Eement Let x=A[1]and set a counter to 1. Starting from A[2],scan the elements one by one increasing the counter by one if the current element is equal to xand decreasing the counter by one if the current element is not equal to x. If all the elements have been scanned and the counter is greater than zero,then return x as the candidate. ■ If the counter becomes 0 when comparing xwith Al,1<n,then call procedure candidate recursively on the elements A+1...n
Finding the Majority Element ◼ Let x=A[1] and set a counter to 1. ◼ Starting from A[2], scan the elements one by one increasing the counter by one if the current element is equal to x and decreasing the counter by one if the current element is not equal to x. ◼ If all the elements have been scanned and the counter is greater than zero, then return x as the candidate. ◼ If the counter becomes 0 when comparing x with A[j], 1<j<n, then call procedure candidate recursively on the elements A[j+1…n]
Finding the Majority E ement Why just return xas a candidate? Restart Count=1 4441235 Count=0 But 5 is not the majority element
Finding the Majority Element ◼ Why just return x as a candidate? 4 4 4 1 2 3 5 Count=0 Count=1 Restart But 5 is not the majority element