编程测试 – Codility – Dominator
我只是遇到了一个问题，给我带来了困难，我仍在努力弄清楚如何满足空间和时间复杂性的限制。
问题如下：数组中的主要成员是占据arrays中一半以上位置的成员，例如：
{3,67,23,67,67}
67是主导成员，因为它在arrays中出现在3/5（> 50％）位置。
现在，您需要提供一个接收数组的方法，如果存在，则返回显性成员的索引，如果没有，则返回-1。
容易，对吗？ 好吧，如果不是因为以下限制，我可以轻松地解决问题：
- 预期时间复杂度为O（n）
- 预期的空间复杂度为O（1）
我可以看到你如何用O（n）空间复杂度来解决这个问题，以及O（1）空间复杂度的O（n ^ 2）时间，但不能同时满足O（n）时间和O（1）空间。
我真的很感激能看到这个问题的解决方案。 别担心，截止日期已经过了几个小时（我只有30分钟），所以我不是想欺骗。 谢谢。
找到BFPRT的中位数，即中位数的中位数（O（N）时间，O（1）空间）。 然后扫描数组 – 如果一个数字占主导地位，则中位数将等于该数字。 遍历数组并计算该数字的实例数。 如果它超过arrays的一半，它就是统治者。 否则，就没有统治者。
谷歌搜索“计算arrays的主导成员”，这是第一个结果 。 请参阅第3页上介绍的算法。
element x; int count ← 0; For(i = 0 to n − 1) { if(count == 0) { x ← A[i]; count++; } else if (A[i] == x) count++; else count−−; } Check if x is dominant element by scanning array A
基本上观察一下，如果你在数组中找到两个不同的元素，你可以删除它们而不改变余数上的主导元素。 这段代码只是不断抛出一对不同的元素，跟踪它看到单个剩余未配对元素的次数。
使用O（1）空间添加Java 100/100 O（N）时间：
https://codility.com/demo/results/demoPNG8BT-KEH/
class Solution { public int solution(int[] A) { int indexOfCandidate = -1; int stackCounter = 0, candidate=-1, value=-1, i =0; for(int element: A ) { if (stackCounter == 0) { value = element; ++stackCounter; indexOfCandidate = i; } else { if (value == element) { ++stackCounter; } else { --stackCounter; } } ++i; } if (stackCounter > 0 ) { candidate = value; } else { return -1; } int countRepetitions = 0; for (int element: A) { if( element == candidate) { ++countRepetitions; } if(countRepetitions > (A.length / 2)) { return indexOfCandidate; } } return -1; } }
如果你想看到它在这里的Java源代码 ，我添加了一些测试用例作为注释作为文件的开头。
得分100％的Java解决方案
public int solution(int[] array) { int candidate=0; int counter = 0; // Find candidate for leader for(int i=0; iarray.length/2 ? candidate : -1; }
这是我的C解决方案得分100％
int solution(int A[], int N) { int candidate; int count = 0; int i; // 1. Find most likely candidate for the leader for(i = 0; i < N; i++){ // change candidate when count reaches 0 if(count == 0) candidate = i; // count occurrences of candidate if(A[i] == A[candidate]) count++; else count--; } // 2. Verify that candidate occurs more than N/2 times count = 0; for(i = 0; i < N; i++) if(A[i] == A[candidate]) count++; if (count <= N/2) return -1; return candidate; // return index of leader }
100％
import java.util.HashMap; import java.util.Map; class Solution { public static int solution(int[] A) { final int N = A.length; Map mapOfOccur = new HashMap((N/2)+1); for(int i=0; i N/2) return i; } return -1; } }
它必须是一个特别好的算法吗？ 😉
static int dominant(final int... set) { final int[] freqs = new int[Integer.MAX_VALUE]; for (int n : set) { ++freqs[n]; } int dom_freq = Integer.MIN_VALUE; int dom_idx = -1; int dom_n = -1; for (int i = set.length - 1; i >= 0; --i) { final int n = set[i]; if (dom_n != n) { final int freq = freqs[n]; if (freq > dom_freq) { dom_freq = freq; dom_n = n; dom_idx = i; } else if (freq == dom_freq) { dom_idx = -1; } } } return dom_idx; }
（ 这主要是为了嘲笑要求 ）
在python中，我们很幸运，一些聪明的人不愿意使用C实现高效的帮助，并将其运送到标准库中。 collections.Counter在这里很有用。
>>> data = [3, 67, 23, 67, 67] >>> from collections import Counter >>> counter = Counter(data) # counter accepts any sequence/iterable >>> counter # dict like object, where values are the occurrence Counter({67: 3, 3: 1, 23: 1}) >>> common = counter.most_common()[0] >>> common (67, 3) >>> common[0] if common[1] > len(data) / 2.0 + 1 else -1 67 >>>
如果你喜欢这里的function就是一个……
>>> def dominator(seq): counter = Counter(seq) common = counter.most_common()[0] return common[0] if common[1] > len(seq) / 2.0 + 1 else -1 ... >>> dominator([1, 3, 6, 7, 6, 8, 6]) -1 >>> dominator([1, 3, 6, 7, 6, 8, 6, 6]) 6
如果一个小技巧没有出现在脑海中，这个问题看起来很难:)。 我在这份可靠性文件中找到了这个技巧： https ：//codility.com/media/train/6-Leader.pdf。
线性解决方案在本文档的底部进行了解释。
我实现了以下java程序，它在同一行上给了我100分。
public int solution(int[] A) { Stack stack = new Stack (); for (int i =0; i < A.length; i++) { if (stack.empty()) stack.push(new Integer(A[i])); else { int topElem = stack.peek().intValue(); if (topElem == A[i]) { stack.push(new Integer(A[i])); } else { stack.pop(); } } } if (stack.empty()) return -1; int elem = stack.peek().intValue(); int count = 0; int index = 0; for (int i = 0; i < A.length; i++) { if (elem == A[i]) { count++; index = i; } } if (count > ((double)A.length/2.0)) return index; else return -1; }
考虑Ruby中的这个100/100解决方案：
# Algorithm, as described in https://codility.com/media/train/6-Leader.pdf: # # * Iterate once to find a candidate for dominator. # * Count number of candidate occurences for the final conclusion. def solution(ar) n_occu = 0 candidate = index = nil ar.each_with_index do |elem, i| if n_occu < 1 # Here comes a new dominator candidate. candidate = elem index = i n_occu += 1 else if candidate == elem n_occu += 1 else n_occu -= 1 end end # if n_occu < 1 end # Method result. -1 if no dominator. # Count number of occurences to check if candidate is really a dominator. if n_occu > 0 and ar.count {|_| _ == candidate} > ar.size/2 index else -1 end end #--------------------------------------- Tests def test sets = [] sets << ["4666688", [1, 2, 3, 4], [4, 6, 6, 6, 6, 8, 8]] sets << ["333311", [0, 1, 2, 3], [3, 3, 3, 3, 1, 1]] sets << ["313131", [-1], [3, 1, 3, 1, 3, 1]] sets << ["113333", [2, 3, 4, 5], [1, 1, 3, 3, 3, 3]] sets.each do |name, one_of_expected, ar| out = solution(ar) raise "FAILURE at test #{name.inspect}: #{out.inspect} not in #{expected.inspect}" if not one_of_expected.include? out end puts "SUCCESS: All tests passed" end
这是Objective-c中易于阅读的100％得分版本
if (A.count > 100000) return -1; NSInteger occur = 0; NSNumber *candidate = nil; for (NSNumber *element in A){ if (!candidate){ candidate = element; occur = 1; continue; } if ([candidate isEqualToNumber:element]){ occur++; }else{ if (occur == 1){ candidate = element; continue; }else{ occur--; } } } if (candidate){ occur = 0; for (NSNumber *element in A){ if ([candidate isEqualToNumber:element]) occur++; } if (occur > A.count / 2) return [A indexOfObject:candidate]; } return -1;
100％得分JavaScript解决方案。 从技术上讲，它是O（nlogn）但仍然通过。
function solution(A) { if (A.length == 0) return -1; var S = A.slice(0).sort(function(a, b) { return a - b; }); var domThresh = A.length/2; var c = S[Math.floor(domThresh)]; var domCount = 0; for (var i = 0; i < A.length; i++) { if (A[i] == c) domCount++; if (domCount > domThresh) return i; } return -1; }
这是VB.NET中100％性能的解决方案。
Dim result As Integer = 0 Dim i, ladderVal, LadderCount, size, valCount As Integer ladderVal = 0 LadderCount = 0 size = A.Length If size > 0 Then For i = 1 To size - 1 If LadderCount = 0 Then LadderCount += 1 ladderVal = A(i) Else If A(i) = ladderVal Then LadderCount += 1 Else LadderCount -= 1 End If End If Next valCount = 0 For i = 0 To size - 1 If A(i) = ladderVal Then valCount += 1 End If Next If valCount <= size / 2 Then result = 0 Else LadderCount = 0 For i = 0 To size - 1 If A(i) = ladderVal Then valCount -= 1 LadderCount += 1 End If If LadderCount > (LadderCount + 1) / 2 And (valCount > (size - (i + 1)) / 2) Then result += 1 End If Next End If End If Return result
查看代码的正确性和性能
以下解决方案解决了复杂度O（N）。
public int solution(int A[]){ int dominatorValue=-1; if(A != null && A.length>0){ Hashtable count=new Hashtable<>(); dominatorValue=A[0]; int big=0; for (int i = 0; i < A.length; i++) { int value=0; try{ value=count.get(A[i]); value++; }catch(Exception e){ } count.put(A[i], value); if(value>big){ big=value; dominatorValue=A[i]; } } } return dominatorValue; }
100％的PHP https://codility.com/demo/results/trainingVRQGQ9-NJP/
function solution($A){ if (empty($A)) return -1; $copy = array_count_values($A); // 3 => 7, value => number of repetition $max_repetition = max($copy); // at least 1 because the array is not empty $dominator = array_search($max_repetition, $copy); if ($max_repetition > count($A) / 2) return array_search($dominator, $A); else return -1; }
我测试我的代码在数组长度在2到9之间的工作正常
public static int sol (int []a) { int count = 0 ; int candidateIndex = -1; for (int i = 0; i a.length/2?candidateIndex:-1; }
@Keith Randall解决方案不适用于{1,1,2,2,3,2,2}
他的解决方案是：
element x; int count ← 0; For(i = 0 to n − 1) { if(count == 0) { x ← A[i]; count++; } else if (A[i] == x) count++; else count−−; } Check if x is dominant element by scanning array A
我把它转换成java如下：
int x = 0; int count = 0; for(int i = 0; i < (arr.length - 1); i++) { if(count == 0) { x = arr[i]; count++; } else if (arr[i] == x) count++; else count--; } return x;
输出：3预期：2
使用O（1）空间添加Java 100/100 O（N）时间：
// you can also use imports, for example: import java.util.Stack; // you can write to stdout for debugging purposes, eg // System.out.println("this is a debug message"); class Solution { public int solution(int[] A) { // write your code in Java SE 8 int count = 0; Stack integerStack = new Stack (); for (int i = 0; i < A.length; i++) { if (integerStack.isEmpty()) { integerStack.push(A[i]); } else if (integerStack.size() > 0) { if (integerStack.peek() == A[i]) integerStack.push(A[i]); else integerStack.pop(); } } if (!integerStack.isEmpty()) { for (int i = 0; i < integerStack.size(); i++) { for (int j = 0; j < A.length; j++) { if (integerStack.get(i) == A[j]) count++; if (count > A.length / 2) return j; } count = 0; } } return -1; } }
这是来自codility的测试结果 。
我认为这个问题已在某个地方得到解决。 “官方”解决方案应该是：
public int dominator(int[] A) { int N = A.length; for(int i = 0; i< N/2+1; i++) { int count=1; for(int j = i+1; j < N; j++) { if (A[i]==A[j]) {count++; if (count > (N/2)) return i;} } } return -1; }
如何排序数组呢？ 然后，比较排序数组的中间和第一个和最后一个元素，以找到主导元素。
public Integer findDominator(int[] arr) { int[] arrCopy = arr.clone(); Arrays.sort(arrCopy); int length = arrCopy.length; int middleIndx = (length - 1) /2; int middleIdxRight; int middleIdxLeft = middleIndx; if (length % 2 == 0) { middleIdxRight = middleIndx+1; } else { middleIdxRight = middleIndx; } if (arrCopy[0] == arrCopy[middleIdxRight]) { return arrCopy[0]; } if (arrCopy[middleIdxLeft] == arrCopy[length -1]) { return arrCopy[middleIdxLeft]; } return null; }
C＃
int dominant = 0; int repeat = 0; int? repeatedNr = null; int maxLenght = A.Length; int halfLenght = A.Length / 2; int[] repeations = new int[A.Length]; for (int i = 0; i < A.Length; i++) { repeatedNr = A[i]; for (int j = 0; j < A.Length; j++) { if (repeatedNr == A[j]) { repeations[i]++; } } } repeatedNr = null; for (int i = 0; i < repeations.Length; i++) { if (repeations[i] > repeat) { repeat = repeations[i]; repeatedNr = A[i]; } } if (repeat > halfLenght) dominant = int.Parse(repeatedNr.ToString());
class Program { static void Main(string[] args) { int []A= new int[] {3,6,2,6}; int[] B = new int[A.Length]; Program obj = new Program(); obj.ABC(A,B); } public int ABC(int []A, int []B) { int i,j; int n= A.Length; for (j=0; j (n / 2)) { Console.WriteLine(finalCount1); Console.ReadLine(); } else { Console.WriteLine("no number found"); Console.ReadLine(); } return -1; } }
在Ruby中你可以做类似的事情
def dominant(a) hash = {} 0.upto(a.length) do |index| element = a[index] hash[element] = (hash[element] ? hash[element] + 1 : 1) end res = hash.find{|k,v| v > a.length / 2}.first rescue nil res ||= -1 return res end
这是我在Java中的答案：我将一个计数存储在单独的数组中，该数组计算输入数组的每个条目的重复项，然后保持指向具有最多重复项的数组位置的指针。 这是支配者。
private static void dom(int[] a) { int position = 0; int max = 0; int score = 0; int counter = 0; int[]result = new int[a.length]; for(int i = 0; i < a.length; i++){ score = 0; for(int c = 0; c < a.length;c++){ if(a[i] == a[c] && c != i ){ score = score + 1; result[i] = score; if(result[i] > position){ position = i; } } } } //This is just to facilitate the print function and MAX = the number of times that dominator number was found in the list. for(int x = 0 ; x < result.length-1; x++){ if(result[x] > max){ max = result[x] + 1; } } System.out.println(" The following number is the dominator " + a[position] + " it appears a total of " + max); }