数组循环右移和约瑟夫环问题

1. 把数组中的每个数循环右移n位，要求时间复杂度O(n)，空间复杂度O(1)

 

package cn.lifx.test;

public class RightMove 
{
	public static void main(String[] args)
	{
		int n = 10;
		int m = 3;
		
		int[] arr = new int[n];
		
		for(int i=0; i<arr.length; i++)
		{
			arr[i] = i;
		}
		
		RightMove rm = new RightMove();
		
		rm.Move(arr, m);
		
		rm.Move2(arr, m);
	}
	
	//时间复杂度为O(n)，空间复杂度O(1)
	public void Move(int[] arr, int n)
	{
		int len = arr.length-1;
		int mid = arr.length/2;
		
		int temp = 0;
		for(int i=0; i<mid; i++)
		{
			temp = arr[i];
			arr[i] = arr[len-i];
			arr[len-i] = temp;
		}
		
		mid = n/2;
		for(int i=0; i<mid; i++)
		{
			temp = arr[i];
			arr[i] = arr[n-i-1];
			arr[n-i-1] = temp;
		}
		
		mid = (arr.length - n)/2 + n;
		for(int i=n; i<mid; i++)
		{
			temp = arr[i];
			arr[i] = arr[len-i+n];
			arr[len-i+n] = temp;
		}
		
		Display(arr);
	}
	
	//时间复杂度为O(n*m)，空间复杂度O(1)
	public void Move2(int[] arr, int n)
	{
		int len = arr.length - 1;
		int temp = 0;
		
		for(int i=0; i<n; i++)
		{
			temp = arr[len];
			for(int j=len; j>0; j--)
			{
				arr[j] = arr[j-1];
			}
			arr[0] = temp;
		}
		
		Display(arr);
	}
	
	public void Display(int[] arr)
	{
		System.out.println();
		for(int i=0; i<arr.length; i++)
		{
			System.out.print(arr[i] + " ");
		}
	}
}

 

 

2. n个人围成一圈，序号依次为0到n-1，从第一个开始报数，到第m个人时他出列，然后从下一个人开始从0计数。问最后一个出列的是谁。

 

package cn.lifx.test;

import java.util.LinkedList;

public class DeleteNum 
{
	public static void main(String[] args)
	{
		int N = 6;
		int M = 4;
		
		DeleteNum delete = new DeleteNum();
		
		int[] arr = new int[N];
		for(int i=0; i<arr.length; i++)
		{
			arr[i] = i;
		}
		
		delete.Delete(arr, N, M);
		
		LinkedList<String> list = new LinkedList<String>();
		for(int i=0; i<N; i++)
		{
			list.add(i+"");
		}
		
		delete.Delete(list, N, M);
	}
	
	public void Delete(int[] arr, int N, int M)
	{
		boolean[] flags = new boolean[arr.length];
		
		for(int i=0; i<flags.length; i++)
		{
			flags[i] = false;
		}
		
		int sum = 0;
		int count = 0;
		int i = 0;
		
		System.out.print("The deleted numbers are: ");
		
		while(sum != N - 1)
		{
			if(!flags[i%N])
			{
				count++;
				
				if(count == M)
				{
					sum++;
					count = 0;
					flags[i%N] = true;
					System.out.print(arr[i%N] + " ");
				}
			}
			
			i++;
		}
		
		for(i=0; i<flags.length; i++)
		{
			if(!flags[i])
			{
				System.out.println("\nThe last number is : " + arr[i]);
				break;
			}
		}
	}
	
	public void Delete(LinkedList<String> list, int N, int M)
	{
		int i = 0;
		int sum = 0;
		int count = 0;
		
		System.out.print("The deleted numbers are: ");
		
		while(sum != N-1)
		{
			count++;
			
			if(count == M)
			{
				System.out.print(list.remove(i%list.size()) + " ");
				
				i--;
				sum++;
				count = 0;
			}
			
			i++;
			
			if(i == list.size())
			{
				i = 0;
			}
		}
		
		System.out.println("\nThe last number is : " + list.getFirst());
	}
}

 

评论

1 楼 form_rr 2009-10-28  

对第一个问题的测试结果:
在n=500000的时候
Move方法和Move2方法速度相当
在n<500000的时候
Move方法比Move2方法慢45%左右
在n>500000的时候
Move方法比Move2方法快,并且随着n越大,越快!