35

我只是遇到了一个代码问题,这让我很难过,我仍在试图弄清楚如何满足空间和时间复杂度的限制。

问题如下:数组中的一个显性成员是占据了数组中一半以上位置的成员,例如:

{3, 67, 23, 67, 67}

67 是主要成员,因为它出现在阵列中的 3/5 (>50%) 位置。

现在,您应该提供一个方法,该方法接收一个数组,如果存在则返回主要成员的索引,如果不存在则返回 -1。

容易,对吧?好吧,如果不是以下限制,我本可以轻松解决问题:

  • 预期时间复杂度为 O(n)
  • 预期空间复杂度为 O(1)

我可以看到你如何在 O(n) 时间和 O(n) 空间复杂度以及 O(n^2) 时间和 O(1) 空间复杂度下解决这个问题,但不是同时满足 O(n) 时间和 O(1) 空间。

我真的很感激看到这个问题的解决方案。别担心,截止日期已经过了几个小时(我只有 30 分钟),所以我不想作弊。谢谢。

4

24 回答 24

47

谷歌搜索“数组的计算主导成员”,这是第一个结果。请参见第 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

基本上观察,如果你在数组中找到两个不同的元素,你可以在不改变剩余元素的主导元素的情况下将它们都删除。这段代码只是不断地抛出成对的不同元素,跟踪它看到单个剩余未配对元素的次数。

于 2012-09-14T03:33:58.343 回答
20

使用BFPRT找到中位数,也就是中位数的中位数(O(N) 时间,O(1) 空间)。然后扫描数组 - 如果一个数字占主导地位,则中位数将等于该数字。遍历数组并计算该数字的实例数。如果它超过数组的一半,它就是支配者。否则,就没有统治者。

于 2012-09-14T02:49:12.983 回答
4

添加具有 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 源代码,我在文件开头添加了一些测试用例作为注释。

于 2015-08-15T13:13:36.600 回答
3

得分 100% 的 Java 解决方案

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;
}
于 2016-03-03T09:30:46.373 回答
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
于 2013-08-26T20:59:21.553 回答
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
}
于 2015-07-28T16:54:50.777 回答
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;
    }
}
于 2016-03-21T22:51:17.077 回答
0

这是一个易于阅读,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;
于 2014-02-01T20:39:17.220 回答
0

它必须是一个特别好的算法吗?;-)

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;
}

这主要是为了取笑要求

于 2012-09-14T02:56:10.867 回答
0

考虑一下 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
于 2014-01-24T22:06:05.697 回答
0

如果没有想到一个小技巧,这个问题看起来很难:)。我在这份 codility 文档中发现了这个技巧: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;
}
于 2013-11-19T20:19:50.983 回答
0

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;
}
于 2015-05-25T21:28:16.973 回答
0

这是 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

查看代码的正确性和性能

于 2015-06-10T23:09:12.670 回答
0

我测试我的代码在 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;
}
于 2017-05-26T20:12:52.063 回答
0

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;

}
于 2015-12-15T15:20:30.203 回答
0

下面的解决方案解决了复杂度 O(N)。

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;
}
于 2015-11-25T14:58:07.940 回答
0

添加具有 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, e.g.
// 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<Integer> integerStack = new Stack<Integer>();
        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的测试结果。

于 2018-03-15T08:49:14.323 回答
-1
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;
    }
}
于 2013-06-26T11:07:00.113 回答
-1

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());
于 2012-11-24T19:31:22.803 回答
-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
于 2013-09-12T07:03:56.730 回答
-1

我认为这个问题已经在某个地方得到了解决。“官方”解决方案应该是:

  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;
  }
于 2012-09-28T07:48:27.093 回答
-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;
}
于 2012-10-06T21:48:18.650 回答
-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

于 2017-10-30T16:56:24.540 回答
-3

这是我在 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);





}
于 2013-01-18T15:19:21.883 回答