路径数组变为统计数组

柔光的暖阳◎ 2022-05-27 00:15 195阅读 0赞

![20180408152008759][]

//路径数组变为统计数组
    public class PathtoArr{
      //*****************************************************
    	//节点的定义
    	public static class Node{
    
              int value;
              Node next;
    
              public Node(int v)
              {
              	this.value=v;
              }
    
    	}
    	//路径数组转换为统计数组
        public static int[]pathsToDistances(int[]paths)
        {
                if(paths==null)
                {
                	 return null;
                }
                int[]distance=new int[paths.length];
                distance[0]=1;
               
                for(int i=0;i<paths.length;i++)
                {
                      if(i!=paths[i])
                      {
                        Node N1=new Node(i);
                        N1.next=new Node(paths[i]);
                      }     
                }
                return null;
        }
        //*********************************************
    
        public static void pathsToNums(int[] paths) {
    		if (paths == null || paths.length == 0) {
    			return;
    		}
    		// citiesPath -> distancesArray
    		pathsToDistans(paths);
    
    		// distancesArray -> numArray
    		distansToNums(paths);
    	}
    
    	public static void pathsToDistans(int[] paths) {
    		int cap = 0;
    		for (int i = 0; i != paths.length; i++) {
    			if (paths[i] == i) {
    				cap = i;
    			} else if (paths[i] > -1) {
    				int curI = paths[i];
    				paths[i] = -1;
    				int preI = i;
    				while (paths[curI] != curI) {
    					if (paths[curI] > -1) {
    						int nextI = paths[curI];
    						paths[curI] = preI;
    						preI = curI;
    						curI = nextI;
    					} else {
    						break;
    					}
    				}
    				int value = paths[curI] == curI ? 0 : paths[curI];
    				while (paths[preI] != -1) {
    					int lastPreI = paths[preI];
    					paths[preI] = --value;
    					curI = preI;
    					preI = lastPreI;
    				}
    				paths[preI] = --value;
    			}
    		}
    		paths[cap] = 0;
    	}
    
    	public static void distansToNums(int[] disArr) {
    		for (int i = 0; i != disArr.length; i++) {
    			int index = disArr[i];
    			if (index < 0) {
    				disArr[i] = 0; // important
    				while (true) {
    					index = -index;
    					if (disArr[index] > -1) {
    						disArr[index]++;
    						break;
    					} else {
    						int nextIndex = disArr[index];
    						disArr[index] = 1;
    						index = nextIndex;
    					}
    				}
    			}
    		}
    		disArr[0] = 1;
    	}
    
    	//打印数组
    	public static void printArr(int []arr)
    	{
    		if(arr==null||arr.length==0)
    		{
    			 return ;
    		}
    		for(int i=0;i!=arr.length;i++)
    		{
    			 System.out.print(arr[i]+" ");
    		}
    		System.out.println();
    
    	}
    	public static void main(String[]args)
    	{
    
    		//System.out.println("Hello");
             int[]paths={9,1,4,9,0,4,8,9,0,1};
             printArr(paths);
             pathsToNums(paths);
             printArr(paths);
    
    	}
    }

![2018040815204466][]

[20180408152008759]: /images/20220527/dc6021edf7cb41b19c51c8c3779a1094.png
[2018040815204466]: /images/20220527/1f02e0c4838a4463ba258e79d412412d.png