我剛剛遇到了一個編碼問題，給了我一個很難的時間，我仍然試圖弄清楚空間和時間複雜性約束是如何實現的。編程測試 - Codility - Dominator
的問題是如下： 陣列中具有支配性的構件是一個佔據在陣列中的一半的位置處，例如：
{3，67，23，67，67}
67是一個主要成員，因爲它以3/5（> 50％）的位置出現在數組中。
現在，您需要提供一個方法，它接受一個數組並返回主成員（如果存在的話）的索引，如果沒有則返回-1。
簡單，對嗎？好吧，我可以輕而易舉地解決了這個問題，如果不是因爲以下限制：
我可以看出如何用O（n）空間複雜度以及具有O（1）空間複雜性的O（n^2）時間來解決O（n）時間問題，但不能同時滿足O（n）時間和O（1）空間。
我真的很感激看到這個問題的解決方案。別擔心，截止日期已經過去了幾個小時（我只有30分鐘），所以我沒有試圖欺騙。謝謝。
查找中位數BFPRT，又名中位數（O（N）時間，O（1）空間）。然後掃描數組 - 如果一個數字佔優勢，則中位數將等於該數字。遍歷數組並計算該數字的實例數。如果它超過陣列的一半，那就是主宰者。否則，沒有統治者。
謝謝，我現在明白了。不過，我無法想象許多程序員會在不知道該算法的情況下管理它。這個問題被評爲「容易」。 – Matthias
@Matthias：這取決於你使用什麼。在Java中可能相當困難（即使你知道正確的算法，在半小時內對它進行編碼可能並不重要）。在C++中，由於標準庫已經有了正確的算法（'std :: nth_element'和'std :: count'），所以它幾乎可笑地變得微不足道，所以大部分工作都由兩行代碼完成（警告：'nth_element' * *也可以使用QuickSelect，它平均是線性的，但是二次最壞的情況）。 –
雖然這是一個有趣的回答這個問題，我相信其他更受歡迎的答案得到我的投票。主要原因是它更容易理解。 – JarJarrr
是否必須特別是好算法？ ;-)
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;
}
（這主要是指在要求取笑）「計算陣列的占主導地位的成員」
哈哈！不錯的一個:) – Matthias
一派，這是first result。見算法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
基本上觀察，如果發現陣列中的兩個不同的元素，你可以刪除它們都沒有對剩餘改變主導成分說明。這段代碼只是拋出一對不同的元素，跟蹤它看到單個剩餘的未配對元素的次數。
我覺得這個問題已經在某個地方解決了。 「官方」解決方案應該是：
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;
}
這個解決方案需要一個排序的數組。 –
我想這個解決方案的時間複雜度遠遠超出了O（N）。 –
如何對數組進行排序？然後比較排序數組的中間和第一個和最後一個元素，以找到主要元素。
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;
}
Arrays.sort（arrCopy）;在最好的情況下是'O（n）'，在一般情況下是'O（n * log n）'。此外，返回的索引與原始索引不匹配。 –
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());
這不是O（N）時間，O（1）空間 – Gisway
這是我的答案在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);
}
它需要是O（N） –
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 ;j++)
{
int count = 1;
for (i = 0; i < n; i++)
{
if ((A[j]== A[i] && i!=j))
{
count++;
}
}
int finalCount = count;
B[j] = finalCount;// to store the no of times a number is repeated
}
// int finalCount = count/2;
int finalCount1 = B.Max();// see which number occurred max times
if (finalCount1 > (n/2))
{ Console.WriteLine(finalCount1); Console.ReadLine(); }
else
{ Console.WriteLine("no number found"); Console.ReadLine(); }
return -1;
}
}
-1：這既不符合時間也不符合空間要求。 –
在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
>>>
如果你喜歡這裏的函數是一個...
>>> 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
計數器使用O（n）空間，而不管它是否由語言的標準庫實現。 – Chandranshu
在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
這個要求如何：「預期的最壞情況空間複雜度是O（1）」？提出的解決方案的空間複雜度至少爲O（N），更不用說它是一個聯想散列。 –
這個問題看起來很難，如果一個小竅門不來心中:)。我在這份密碼文件中發現了這個技巧：https://codility.com/media/train/6-Leader.pdf。
線性解決方案在本文檔的底部進行了解釋。
我實現了下面的java程序，它在同一行上給了我100分。
public int solution(int[] A) {
Stack<Integer> stack = new Stack<Integer>();
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;
}
考慮紅寶石此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
這是一個易於閱讀，100％得分的版本在Objective-C
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
這裏是我的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
}
添加一個Java 100/100 O（N）的時間與O（1）空間：
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 source code it's here，我添加了一些測試用例作爲註釋作爲文件的開頭。
下面的解決方案解決複雜度O（N）。在PHP
public int solution(int A[]){
int dominatorValue=-1;
if(A != null && A.length>0){
Hashtable<Integer, Integer> 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％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;
}
Java解決方案與得分100％
public int solution(int[] array) {
int candidate=0;
int counter = 0;
// Find candidate for leader
for(int i=0; i<array.length; i++){
if(counter == 0) candidate = i;
if(array[i] == array[candidate]){
counter++;
}else {
counter--;
}
}
// Count candidate occurrences in array
counter = 0;
for(int i=0; i<array.length; i++){
if(array[i] == array[candidate]) counter++;
}
// Check that candidate occurs more than array.lenght/2
return counter>array.length/2 ? candidate : -1;
}
100％
import java.util.HashMap;
import java.util.Map;
class Solution {
public static int solution(int[] A) {
final int N = A.length;
Map<Integer, Integer> mapOfOccur = new HashMap((N/2)+1);
for(int i=0; i<N; i++){
Integer count = mapOfOccur.get(A[i]);
if(count == null){
count = 1;
mapOfOccur.put(A[i],count);
}else{
mapOfOccur.replace(A[i], count, ++count);
}
if(count > N/2)
return i;
}
return -1;
}
}
你製作了一張地圖。空間複雜性不是O（1） –
測試我的代碼在陣列其做工精細長度在2到9之間
public static int sol (int []a)
{
int count = 0 ;
int candidateIndex = -1;
for (int i = 0; i <a.length ; i++)
{
int nextIndex = 0;
int nextOfNextIndex = 0;
if(i<a.length-2)
{
nextIndex = i+1;
nextOfNextIndex = i+2;
}
if(count==0)
{
candidateIndex = i;
}
if(a[candidateIndex]== a[nextIndex])
{
count++;
}
if (a[candidateIndex]==a[nextOfNextIndex])
{
count++;
}
}
count -- ;
return count>a.length/2?candidateIndex:-1;
}
@Keith蘭德爾解決方案是不工作{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
你使用什麼語言？ – Kyle
我正在使用java。 – Matthias
我真的很好奇真正的測試有什麼問題嗎？作爲一名Java開發人員（主要是開發企業系統），我一直工作了5年，而不是真的需要解決像這樣的問題！ – Adelin