|
Don't just follow the path. Make your own trail.
不要隨波逐流,，要找到自己的路,。 給你一個整數(shù)數(shù)組arr,。請你將數(shù)組中的元素按照其二進制表示中數(shù)字1的數(shù)目升序排序,。 如果存在多個數(shù)字二進制中1的數(shù)目相同，則必須將它們按照數(shù)值大小升序排列,。 請你返回排序后的數(shù)組,。
示例 1： 輸入：arr = [0,1,2,3,4,5,6,7,8] 輸出：[0,1,2,4,8,3,5,6,7] 解釋：[0] 是唯一一個有 0 個 1 的數(shù)。 [1,2,4,8] 都有 1 個 1 ,。 [3,5,6] 有 2 個 1 ,。 [7] 有 3 個 1 。 按照 1 的個數(shù)排序得到的結(jié)果數(shù)組為 [0,1,2,4,8,3,5,6,7]
示例 2： 輸入：arr = [1024,512,256,128,64,32,16,8,4,2,1] 輸出： [1,2,4,8,16,32,64,128,256,512,1024] 解釋：數(shù)組中所有整數(shù)二進制下都只有 1 個 1 ,，所以你需要按照數(shù)值大小將它們排序,。
示例 3： 輸入：arr = [10000,10000] 輸出：[10000,10000]
示例 4： 輸入：arr = [2,3,5,7,11,13,17,19] 輸出：[2,3,5,17,7,11,13,19]
示例 5： 輸入：arr = [10,100,1000,10000] 輸出：[10,100,10000,1000]
提示： 1 <= arr.length <= 500
0 <= arr[i] <= 10^4
這道題是讓求數(shù)組中每個數(shù)字二進制中1的個數(shù)，然后以1的個數(shù)從大到小排序,，如果1的個數(shù)相同,，就按照原來數(shù)字的大小進行排序。
我們仔細看這題有個限制條件就是0<=arr[i]<=10^4,，也就是說數(shù)組元素都是非負數(shù),，并且都是小于等于10000的。不知道大家有沒有學(xué)Android的,，看過Android源碼,，你會看到里面經(jīng)常會用一個數(shù)字表示多種狀態(tài)，有的是用二進制中某一位來表示,，有的是用二進制中的多位來表示,，看到這里是不是也有了靈感。
所以一種最簡單的方式,，先計算出數(shù)組中每個元素二進制中1的個數(shù)乘以100000+原來的數(shù),，讓他成為一個新的數(shù)，接著再對他們進行排序,，最后再還原,，看下代碼
1public int[] sortByBits(int[] arr) {
2 int length = arr.length;
3 //數(shù)組中每個數(shù)字的二進制位乘以100000再加上原來的數(shù)值，
4 //成為一個新的數(shù)
5 for (int i = 0; i < length; i++) {
6 arr[i] = Integer.bitCount(arr[i]) * 100000 + arr[i];
7 }
8 //對這個新的數(shù)進行排序
9 Arrays.sort(arr);
10 //然后再把新的數(shù)字還原成原來的數(shù)字
11 for (int i = 0; i < length; i++) {
12 arr[i] %= 100000;
13 }
14 return arr;
15}
385,，位1的個數(shù)系列（二）
402，位1的個數(shù)系列（三）
關(guān)于排序,，在兩年前寫過十幾種排序算法,，也可以看下 101，排序-冒泡排序
102,，排序-選擇排序
103,，排序-插入排序
104，排序-快速排序
105,，排序-歸并排序
106,，排序-堆排序
107，排序-桶排序
108,，排序-基數(shù)排序
109,，排序-希爾排序
110，排序-計數(shù)排序
111,，排序-位圖排序
112,，排序-其他排序
如果這樣兩者結(jié)合的話，那么答案就比較多了,，我們來隨便挑一組組合,。排序就使用插入排序，計算二進制中1的個數(shù)我們隨便挑一個，答案如下 1public int[] sortByBits(int[] arr) {
2 //二維數(shù)組,，temp[i][0]存儲的是當(dāng)前的值
3 //temp[i][1]存儲的是當(dāng)前值的二進制中1的個數(shù)
4 int[][] temp = new int[arr.length][2];
5 for (int i = 0; i < arr.length; i++) {
6 temp[i][0] = arr[i];
7 temp[i][1] = hammingWeight(arr[i]);
8 }
9 //使用插入排序
10 insertSort(temp);
11 for (int i = 0; i < arr.length; i++) {
12 arr[i] = temp[i][0];
13 }
14 return arr;
15}
16
17//插入排序
18private void insertSort(int[][] array) {
19 for (int i = 1; i < array.length; i++) {
20 int j;
21 int[] temp = array[i];
22 for (j = i - 1; j >= 0; j--) {
23 //先比較位1的大小,，如果相同再比較數(shù)字的大小
24 if (array[j][1] > temp[1] || (array[j][1] == temp[1] && array[j][0] > temp[0])) {
25 array[j + 1] = array[j];//往后挪
26 } else {
27 break;//沒有交換就break
28 }
29 }
30 array[j + 1] = temp;
31 }
32}
33
34//計算二進制中1的個數(shù)
35public int hammingWeight(int n) {
36 int count = 0;
37 while (n != 0) {
38 n &= n - 1;
39 count++;
40 }
41 return count;
42}
這題結(jié)合了計算二進制中1的個數(shù)和排序兩種方式，這兩種方式之前都有大量的介紹,，如果結(jié)合寫的話,，答案還是比較多的。
|
