Example:
Input: arr[] = {4, 3, 7, 8, 6, 2, 1}
Output: arr[] = {3, 7, 4, 8, 2, 6, 1}
Input: arr[] = {1, 4, 3, 2}
Output: arr[] = {1, 4, 2, 3}
Input: [-3, -2, 0, 3, 4, 5] Output: 5 There are 5 distinct absolute values among the elements of this array, i.e. 0, 2, 3, 4 and 5) Input: [-1, -1, -1, -1, 0, 1, 1, 1, 1] Output: 2 Input: [-1, -1, -1, -1, 0] Output: 2 Input: [0, 0, 0] Output: 1http://www.geeksforgeeks.org/absolute-distinct-count-array-sorted-absolute-values/
Input: [6, 8, 4, 5, 2, 3] Output: 604 The minimum sum is formed by numbers 358 and 246 Input: [5, 3, 0, 7, 4] Output: 82 The minimum sum is formed by numbers 35 and 047
Find popular item in sorted array of natural numbers.This is actually a very interesting problem. Since the popular item is defined as the element is repeated more than 1 / 4 times, and since it is a sorted array, so it can only occurs on 0, n / 4, n /2 and 3n/4 index. And the rest is just do binary search and get the range.
An item is popular is if its repeated n/4 times or more.
For Ex:
Input: 123444445678
Popular item is 4.
Liner scan is O(n), but solution needs to be in O(logN) complexity and O(1) space complexity.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| public class PopularNumber { public static void popular(int[] n){ if(n == null || n.length == 0) return; int len = n.length; int[] check = {0, len / 4, len / 2, 3 * len / 4}; for(int i = 0; i < 4; i++){ if(i > 0 && n[check[i]] == n[check[i - 1]]) continue; int l = check[i]; int start = binarySearchStart(n, n[l]); int end = binarySearchEnd(n, n[l]); //need to be larger than the ceil in case len / 4.0 is not an integer if(end - start + 1 >= Math.ceil(len / 4.0)) System.out.println(n[l]); } } private static int binarySearchEnd(int[] n, int target){ int len = n.length; int start = 0; int end = len - 1; while(start + 1 < end){ int mid = (start + end) / 2; if(n[mid] <= target) start = mid; else end = mid; } if(n[end] == target) return end; else return start; } private static int binarySearchStart(int[] n, int target){ int len = n.length; int start = 0; int end = len - 1; while(start + 1 < end){ int mid = (start + end) / 2; if(n[mid] >= target) end = mid; else start = mid; } if(n[start] == target) return start; else return end; } public static void main(String[] args) { //int[] n = {1, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8}; int[] n = {1, 1, 2, 3, 4}; popular(n); }} |
