题目:给定一个长度为N的数组,里面的每一个元素的值都在0到N-1之间,并且
数组的元素是各不相同的。重新排列这个数组,使得array[i]的值变成array[array[i]], 但是只能使用
0(1)的额外空间。
实现的代码如下:
import java.util.Arrays;
/**
* <pre>
* 题目要求:重新排列一个数组,使得array[i]的值变成array[array[i]],
* 只能使用0(1)的额外空间。
*
* 題目描述:给定一个长度为N的数组,里面的每一个元素的值都在0到N-1之间,并且数组的元素是各不相同的。重新排列
* 这个数组,使得array[i]的值变成array[array[i]], 但是只能使用0(1)的额外空间。
* </pre>
*
* 例如:
*
* {3, 2, 0, 1} ==> {1, 0, 3, 2}
*
* {4, 0, 2, 1, 3} ==> {3, 4, 2, 0, 1}
*
* {0, 1, 2, 3} ==> {0, 1, 2, 3}
*
* ...
*
* @author Eric
*
*/
public class RearrangeArray {
/**
* 重新排列一个给定的数组,使得array[i]的值变成array[array[i]], 但是只能使用0(1)的额外空间。
*/
public int[] rearrange(int[] array) {
if (null == array) {
throw new IllegalArgumentException("数组不是为NULL.");
}
if (!(isArrayExpected(array.clone()))) {
throw new IllegalArgumentException(
"长度为N的数组,里面的每一个元素的值都在0到N-1之间,并且数组的元素是各不相同的。");
}
int len = array.length;
/*
* 每个位置的元素都增加一个值,这个值为(array[array[i]] % N) * N
*
* 这样做的好处是让每个元素同时拥有旧的和新的值。
*
* oldValue = array[i] % N, newValue = array[i] / N
*/
for (int i = 0; i < len; i++) {
array[i] += (array[array[i]] % len) * len;
}
/*
* 计算新的值,newValue = array[i] / N
*/
for (int i = 0; i < len; i++) {
array[i] /= len;
}
return array;
}
/**
* 判断待处理的整形数组其所拥有的元素是否符合要求。
*/
private boolean isArrayExpected(int[] array) {
Arrays.sort(array);
/*
* 如果是符合要求数组,那么其排序后的结果将会是{0,1,2,3,...N-1}
*/
for (int i = 0; i < array.length; i++) {
if (i != array[i]) {
return false;
}
}
return true;
}
}
一个测试例子如下:
import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] origArray = { 3, 2, 0, 1 };
System.out.printf("原数组的内容是%s\n", Arrays.toString(origArray));
RearrangeArray ra = new RearrangeArray();
System.out.printf("变换后的数组内容是%s\n",
Arrays.toString(ra.rearrange(origArray)));
}
}
运行结果如下:
原数组的内容是[3, 2, 0, 1]
变换后的数组内容是[1, 0, 3, 2]
分享到:
相关推荐
如果要在某个数组中删除一个元素,可以直接用的unset,但是数组的索引不会重排: <?php $arr = array('a','b','c','d'); unset($arr[1]); print_r($arr); ?> 结果是: Array ( [0] => a [2] => c [3] => d ...
茴香豆的“茴”字有四种写法,PHP从数组中删除元素也有四种方法 ^_^。 删除一个元素,且保持原有索引不变 ...如果打算重排索引(让索引从0开始,并且连续),可以使用 array_values 函数: $array = array_values
复制代码 代码如下: function array_sort($array, $key){ if(is_array($array)){ ...for( $i = 0; $i < count xss=removed xss=removed xss=removed> $v){ $new_array[$j] = $array[$v]; $j++; } uns
本文实例讲解了PHP数组排序中sort、asort与ksort的用法,供大家参考借鉴之用。具体实例如下所示: <?php $arr = array('d'=>'sdf', 'r'=>'sdf', 'a'=> 'eee'); //sort($arr); // 对数组的值进行重排, 删除之前的...
主要介绍了PHP使用array_merge重新排列数组下标的方法,以实例形式较为详细的分析了array_merge的功能,及针对数组下标进行重新排列操作的实现技巧,需要的朋友可以参考下
本文介绍了利用Array.prototype.sort方法和Math.random()实现快速打乱数组的方法,大家参考使用吧
i < array.Length - 1 ; i++) { for (int j = i + 1 ; j < array.Length ; j++) { if (array[j] < array) { temp = array ; array = array[j] ; array[j] = temp ; } } } 9.描述一下C#中索引器的实现...
10.2.3 重排容器元素的算法 342 10.3 定制操作 344 10.3.1 向算法传递函数 344 10.3.2 lambda表达式 345 10.3.3 lambda捕获和返回 349 10.3.4 参数绑定 354 10.4 再探迭代器 357 10.4.1 插入迭代器 ...
16.2.2 0/1背包问题 503 16.2.3 最大完备子图 506 16.2.4 旅行商问题 508 16.2.5 电路板排列 510 第17章 分枝定界 516 17.1 算法思想 516 17.2 应用 519 17.2.1 货箱装船 519 17.2.2 0/1背包问题 526 17.2.3 最大...
10.2.3 重排容器元素的算法 342 10.3 定制操作 344 10.3.1 向算法传递函数 344 10.3.2 lambda表达式 345 10.3.3 lambda捕获和返回 349 10.3.4 参数绑定 354 10.4 再探迭代器 357 10.4.1 插入迭代器 ...
16.2.2 0/1背包问题 503 16.2.3 最大完备子图 506 16.2.4 旅行商问题 508 16.2.5 电路板排列 510 第17章 分枝定界 516 17.1 算法思想 516 17.2 应用 519 17.2.1 货箱装船 519 17.2.2 0/1背包问题 526 17.2.3 最大...
13.3.2 0/1背包问题 410 13.3.3 拓扑排序 412 13.3.4 二分覆盖 415 13.3.5 单源最短路径 421 13.3.6 最小耗费生成树 424 13.4 参考及推荐读物 433 第14章 分而治之算法 434 14.1 算法思想 434 14.2 应用 440 14.2.1...
13.3.2 0/1背包问题 410 13.3.3 拓扑排序 412 13.3.4 二分覆盖 415 13.3.5 单源最短路径 421 13.3.6 最小耗费生成树 424 13.4 参考及推荐读物 433 第14章 分而治之算法 434 14.1 算法思想 434 14.2 应用 440 14.2.1...
13.3.2 0/1背包问题 410 13.3.3 拓扑排序 412 13.3.4 二分覆盖 415 13.3.5 单源最短路径 421 13.3.6 最小耗费生成树 424 13.4 参考及推荐读物 433 第14章 分而治之算法 434 14.1 算法思想 434 14.2 应用 440 14.2.1...
讲述了c++的各种使用的数据结构和算法,对于初学者和已经入门的都很有帮助,里面的内容有 目 录 译者序 前言 第一部分 预备知识 第1章 C++程序设计 1 1.1 引言 1 1.2 函数与参数 2 1.2.1 传值参数 2 1.2.2 模板函数 ...
13.3.2 0/1背包问题 410 13.3.3 拓扑排序 412 13.3.4 二分覆盖 415 13.3.5 单源最短路径 421 13.3.6 最小耗费生成树 424 13.4 参考及推荐读物 433 第14章 分而治之算法 434 14.1 算法思想 434 14.2 应用 440 14.2.1...
13.3.2 0/1背包问题 410 13.3.3 拓扑排序 412 13.3.4 二分覆盖 415 13.3.5 单源最短路径 421 13.3.6 最小耗费生成树 424 13.4 参考及推荐读物 433 第14章 分而治之算法 434 14.1 算法思想 434 14.2 应用 440 14.2.1...
13.3.2 0/1背包问题 410 13.3.3 拓扑排序 412 13.3.4 二分覆盖 415 13.3.5 单源最短路径 421 13.3.6 最小耗费生成树 424 13.4 参考及推荐读物 433 第14章 分而治之算法 434 14.1 算法思想 434 14.2 应用 440 14.2.1...
16.2.2 0/1背包问题 503 16.2.3 最大完备子图 506 16.2.4 旅行商问题 508 16.2.5 电路板排列 510 第17章 分枝定界 516 17.1 算法思想 516 17.2 应用 519 17.2.1 货箱装船 519 17.2.2 0/1背包问题 526 ...