Find the maximum repeating number in O(n) time and O(1) extra space

  • amethlex
  • 14 Nov 2016
  •   Comments Off on Find the maximum repeating number in O(n) time and O(1) extra space
illust_global05

题目:
Given an array of size n, the array contains numbers in range from 0 to k-1 where k is a positive integer and k <= n. Find the maximum repeating number in this array. For example, let k be 10 the given array be arr[] = {1, 2, 2, 2, 0, 2, 0, 2, 3, 8, 0, 9, 2, 3}, the maximum repeating number would be 2. Expected time complexity is O(n) and extra space allowed is O(1). Modifications to array are allowed.

思路:类似于bucket sort。

代码:

public class Solution {
	public static int[] find(int[] input, int k)
	{
		for(int i = 0; i < input.length ;i++)
		{
			input[input[i] % k] += k;
		}
		int max = input[0];
		input[0] %= k;
		int index = 0;
		for(int i = 1; i < input.length; i++) { if(input[i] > max)
			{
				max = input[i];
				index = i;
			}
			input[i] %= k;
		}
		int count = 0;
		for(int i: input) if(i == index) count++;
		return new int[]{index, count};
		
	}
	public static void main(String[] args)
	{
		int[] input = {2, 3, 3, 5, 3, 4, 1, 5};
		int k = 6;
		int[] output = find(input, k);
		System.out.println("" + output[0] + " " + output[1]);
		
	}
}

输出:

3
3

1725total visits,4visits today