米拓世纪初试

待我称王封你为后i 2021-09-19 07:18 255阅读 0赞

米拓世纪初试笔记；

两道编程题：

### 给定一个由正数,负数和0组成的整数数组,将所有为0的元素,挪到数组末尾。要求时间复杂度O(n) ###

> 解题思路：采用左右指针，同时向中间遍历，这样只需要遍历一遍数组就可以完成

/** * @author chen */
    public class Main { 
    
        /** * 一个由正数,负数和0组成的整数数组,将所有为0的元素,挪到数组末尾 * * @param array 整数数组 */
        public void moveNumber(int[] array) { 
            int left = 0;
            int right = array.length - 1;
            while (left < right) { 
                // 从左往右查找一个 0 的元素
                while (array[left] != 0) { 
                    left++;
                }
                // 从右往左查找一个非 0 元素
                while (array[right] == 0) { 
                    right--;
                }
                if (left < right) { 
                    // 交换两个数
                    array[left] = array[left] ^ array[right];
                    array[right] = array[left] ^ array[right];
                    array[left] = array[left] ^ array[right];
                }
            }
        }
    }

### 给定任意一个自然数，获取它重新排列后，下一个比它大的自然数，要求时间复杂度O(n)。例如： ###

给定1233,它的下一个是1323；
        给定1323,它的下一个是1332；
        给定9876,它的下一个不存在；
        请设计一个函数，完成此功能。

> 解题思路：将数字转换成数组，从右往左查找第一个前一个数字比后一个小的位置，如果存在交换两个数字，如果不存在就返回-1

/** * @author chen */
    public class Main { 
        /** * 获取它重新排列后，下一个比它大的自然数，如果不存在则返回-1 * * @param number 数字 * @return 下一个比他大的自然数 */
        private int nextNumber(int number) { 
            int[] array = numberToArray(number);
            if (array.length == 1) { 
                return -1;
            }
            // 调换位置开始的地方，后一个数比前一个数大
            int i = -1;
            boolean flag = false;
            for (i = array.length - 1; i > 0; i--) { 
                if (array[i] > array[i - 1]) { 
                    flag = true;
                    break;
                }
            }
            // 交换位置
            if (flag) { 
                array[i] = array[i] ^ array[i - 1];
                array[i - 1] = array[i] ^ array[i - 1];
                array[i] = array[i] ^ array[i - 1];
                // 组合数字
                int sum = 0;
                for (int value : array) { 
                    sum = sum * 10 + value;
                }
                return sum;
            }
            return -1;
        }
    
        /** * 将一个数字转换成数组 * * @param number 数字——数字为自然数 * @return 数字数组 */
        private int[] numberToArray(int number) { 
            if (number == 0) { 
                return new int[1];
            }
            int[] temp = new int[100];
            int index = 0;
            while (number > 0) { 
                int t = number % 10;
                temp[index++] = t;
                number /= 10;
            }
            System.out.println(index);
            int[] array = new int[index];
            for (int i = 0, j = index - 1; i < index; i++, j--) { 
                array[i] = temp[j];
            }
            return array;
        }
    }