题目 https://leetcode-cn.com/problems/sort-integers-by-the-number-of-1-bits/
int countone(int n) { int count = 0; for(;n>0;count++,n&=(n-1)){} return count; } int search(int* nums,int left,int right,int target) { int middle; while(left<=right) { middle = (left+right)/2; if(nums[middle] == target) { left = middle; break; } else if(nums[middle] > target) { right = middle-1; } else { left = middle+1; } } return left; } int* sortByBits(int* arr, int arrSize, int* returnSize){ int index[33][2] = {0};//记录每个1,拥有的个数的index和长度len int i,j,n; int indexStart,indexLen; int *returnNums = malloc(sizeof(int)*(arrSize+1)); *returnSize = arrSize; for(i=0;i<arrSize;i++) { n = countone(arr[i]);//1个个数 indexStart = index[n][0];//开始 indexLen = index[n][1];//长度 j = search(returnNums,indexStart,indexStart + indexLen -1,arr[i]);//查找插入的位置 memmove(&returnNums[j+1],&returnNums[j],sizeof(int)*(i-j));//移位 returnNums[j] = arr[i];//赋值 index[n][1] +=1;//长度+1 for(j=n+1;j<33;j++) index[j][0]+=1;//剩下的index位置+1 } return returnNums; }
